2019 牛客多校第十场

Coffee Chicken

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 524288K,其他语言1048576K
64bit IO Format: %lld

题目描述

Dr. JYY has just created the Coffee Chicken strings, denoted as S(n). They are quite similar to the Fibonacci soup — today’s soup is made by mingling yesterday’s soup and the day before yesterday’s soup:
– S(1)=”COFFEE”S(1) = \texttt{“COFFEE”}S(1)=”COFFEE”;
– S(2)=”CHICKEN”S(2) = \texttt{“CHICKEN”}S(2)=”CHICKEN”;
– S(n) = S(n-2) :: S(n-1), where :: denotes string concatenation.
The length of S(n) quickly gets out of control as n increases, and there would be no enough memory in JYY’s game console to store the entire string. He wants you to find 10 contiguous characters in S(n), starting from the kth character.

输入描述:

The first line of input is a single integer T (1≤T≤1000)(1 \leq T \leq 1000)(1≤T≤1000), denoting the number of test cases. Each of the following T lines is a test case, which contains two integers n, k (1≤n≤500,1≤k≤min⁡{∣S(n)∣,1012})(1 \leq n \leq 500, 1 \leq k \leq \min\{|S(n)|, 10^{12}\})(1≤n≤500,1≤k≤min{∣S(n)∣,1012}). |S| denotes the length of string S.

输出描述:

For each test case, print the answer in one line. If there are no enough characters from the kth character, output all characters until the end of the string.

示例1

输入

2
3 4
2 7

输出

FEECHICKEN
N

签到题,分治

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
ll n,k,len[60],lim;
string s[3];
void work(int n,ll l,ll r){
    if(n==1||n==2){
        rep(i,l,r) printf("%c",s[n][i-1]);
        return;
    }
    if(l>len[n-2]) work(n-1,l-len[n-2],r-len[n-2]);
    else if(r<=len[n-2]) work(n-2,l,r);
    else{
        work(n-2,l,len[n-2]);work(n-1,1,r-len[n-2]);
    }
}
void solve(){
    scanf("%lld%lld",&n,&k);
    if(n>57){
        if(n%2) n=57;
        else n=56;
    }
    lim=min(k+9,len[n]);
    work(n,k,lim); puts("");
}
int main(){
    s[1]="COFFEE";s[2]="CHICKEN";
    len[1]=6;len[2]=7;
    rep(i,3,58) len[i]=len[i-1]+len[i-2];
    int T;cin>>T;
    while(T--) solve();
}

 


Han Xin and His Troops

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 524288K,其他语言1048576K
64bit IO Format: %lld

题目描述

His majesty chatted with Han Xin about the capabilities of the generals. Each had their shortcomings. His majesty asked, “How many troops could I lead?” Han Xin replied, “Your highness should not lead more than 100000.” His majesty said, “And what about you?” “For your humble servant, the more the merrier!” said Han Xin.

—Records of the Grand Historian

Han Xin was a military general who served Liu Bang during the Chu-Han contention and contributed greatly to the founding of the Han dynasty. Your friend, in a strange coincidence, also named Han Xin, is a military general as well.

One day you asked him how many troops he led. He was reluctant to tell you the exact number, but he told you some clues in certain form, for example:
– if we count the troops by threes, we have two left over;
– if we count by fives, we have three left over;
– if we count by sevens, two are left over;
– …
You wonder the number of his troops, or he was simply lying. More specifically, you would like to know the minimum possible number of troops he leads, and if the minimum number is too large, then you suspect he was lying.

输入描述:

The first line of input contains two integers n, m (1≤n≤100,1≤m≤1018)(1 \leq n \leq 100, 1 \leq m \leq 10^{18})(1≤n≤100,1≤m≤1018), the number of clues he told you and the threshold that you think he was probably lying.

The remaining part of the input are n lines, specifying the clues, Each line consists of two integers a, b (0≤b<a<105)(0 \leq b < a < 10^5)(0≤b<a<105), representing a clue that b troops are left over if we count them by a's.

输出描述:

If there does not exist a non-negative number of troops satisfying all clues, print he was definitely lying\texttt{he was definitely lying}he was definitely lying; otherwise, if the minimum non-negative possible number of troops is greater than m, print he was probably lying\texttt{he was probably lying}he was probably lying; otherwise, print the minimum non-negative number.

示例1

输入

3 100
3 2
5 3
7 2

输出

23

示例2

输入

4 10000
12 7
15 2
30 5
8 6

输出

he was definitely lying

示例3

输入

2 10
11 3
19 7

输出

he was probably lying

exgcd模版题,但是要用到大数

import java.io.*;
import java.util.Scanner;
import java.math.*;
public class Main {
    public static BigInteger[] a=new BigInteger[111];
    public static BigInteger[] r=new BigInteger[111];
    static BigInteger x,y;
    static BigInteger exgcd(BigInteger a,BigInteger b) {
        BigInteger r,q,s1=BigInteger.valueOf(1),s2=BigInteger.valueOf(0);
        if(b.equals(BigInteger.valueOf(0))) {
            x=BigInteger.valueOf(1);y=BigInteger.valueOf(0);
            return a;
        }
        x=BigInteger.valueOf(0);y=BigInteger.valueOf(1);
        r=a.mod(b); q=a.divide(b);
        while(r.compareTo(BigInteger.valueOf(0))==1) {
            BigInteger m=x,n=y;
            x=s1.subtract(x.multiply(q));
            y=s2.subtract(y.multiply(q));
            s1=m;s2=n;a=b;b=r;
            q=a.divide(b);r=a.mod(b);
        }
        return b;
    }
    static BigInteger excrt(int n) {
        BigInteger M=a[1],R=r[1],d;
        for (int i=2;i<=n;i++) {
            d=exgcd(M,a[i]);
            BigInteger tmp=R.subtract(r[i]);
            BigInteger res=tmp.mod(d);
            if (res.compareTo(BigInteger.valueOf(0))==1) return BigInteger.valueOf(-1);
            x=tmp.divide(d).multiply(x).mod(a[i]);
            BigInteger kk=M.multiply(x);
            R=R.subtract(kk);
            M=M.divide(d).multiply(a[i]);
            R.add(M); R.mod(M);
        }
        BigInteger ans=R.mod(M);
        ans.add(M);ans.mod(M);
        return ans;
    }
    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        int n; BigInteger mm;
        n=cin.nextInt();mm=cin.nextBigInteger();
        for(int i=1;i<=n;i++) {
            a[i]=cin.nextBigInteger();
            r[i]=cin.nextBigInteger();
        }
        BigInteger ans=excrt(n);
        if (ans.equals(BigInteger.valueOf(-1))) System.out.println("he was definitely lying");
        else if (ans.compareTo(mm)==1) System.out.println("he was probably lying");
        else System.out.println(ans);
    }
}

 


Hilbert Sort

时间限制:C/C++ 6秒,其他语言12秒
空间限制:C/C++ 524288K,其他语言1048576K
64bit IO Format: %lld

题目描述

The Hilbert curve, invented by the German mathematician David Hilbert, is one of the most famous fractal curves. The i-th Hilbert curve gives a sequential ordering of the cells in a 2i×2i2^i \times 2^i2i×2i grid.

The formal definition of Hilbert curves is recursive. The i-th Hilbert curve can be formed by connecting four (i-1)-th Hilbert curves, in the following way:
1. partition the 2i×2i2^i \times 2^i2i×2i grid into four 2i−1×2i−12^{i-1} \times 2^{i-1}2i−1×2i−1 quadrants;
2. reflect an (i-1)-th Hilbert curve across the main diagonal (from top left to bottom right), and place it in the upper left quadrant;
3. place two copies of the (i-1)-th Hilbert curve in the lower left and lower right quadrants, respectively;
4. reflect an (i-1)-th Hilbert curve across the secondary diagonal (from top right to bottom left), and place it in the upper right quadrant.
The first three Hilbert curves are shown below.

The Hilbert sort, just as the name implies, is to sort a set of the cells according to the Hilbert curve. A cell is ranked before another if it is encountered earlier when walking along the Hilbert curve. The Hilbert sort is widely used in many areas, because such sort maps a set of 2-dimensional data points into 1-dimensional space, with spatial locality preserved fairly well.

Give you an integer k and a set of cells in the 2k×2k2^k \times 2^k2k×2k grid, please sort them in the order induced from the k-th Hilbert curve.

输入描述:

The first line contains two integers n, k (1≤n≤106,1≤k≤30)(1 \leq n \leq 10^6, 1 \leq k \leq 30)(1≤n≤106,1≤k≤30), the number of cells to sort and the order of the Hilbert curve.

The next n lines, each containing two integers xi,yix_i, y_ixi​,yi​ (1≤xi,yi≤2k)(1 \leq x_i, y_i \leq 2^k)(1≤xi​,yi​≤2k), denoting the cell in the xix_ixi​-th row and the yiy_iyi​-th column. All cells in the input are distinct.

输出描述:

Output the coordinates of the sorted cells in n lines.

示例1

输入

5 2
2 4
2 3
1 1
3 1
4 3

输出

1 1
3 1
4 3
2 4
2 3

示例2

输入

4 1
1 1
1 2
2 1
2 2

输出

1 1
2 1
2 2
1 2

题目给出的是“希尔伯特曲线”,属于“分形”。给所有点编码,具体可以递归实现,用get(x,yk)表示大小为2^k的希尔伯特曲线中(x,y)号点的坐标。然后讨论(x,y)在四个角的情况,然后进行一定的坐标变换即可。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
struct node{
	int x,y;
	ll id;
	bool operator < (const node &b) const{
        return id < b.id;
    }
}p[maxn];
ll dfs(int n,int x,int y){
	if(n==0) return 1;
	int m=1<<(n-1);
	if(x<=m && y<=m) return dfs(n-1,y,x);
	if(x>m && y<=m) return 3ll*m*m+dfs(n-1,m-y+1,m*2-x+1);
	if(x<=m && y>m) return 1ll*m*m+dfs(n-1,x,y-m);
	if(x>m && y>m) return 2ll*m*m+dfs(n-1,x-m,y-m);
}
void solve(){
	int n,k;scanf("%d%d",&n,&k);
	rep(i,1,n){
		scanf("%d%d",&p[i].x,&p[i].y);
		p[i].id=dfs(k,p[i].y,p[i].x);
	} sort(p+1,p+n+1);
	rep(i,1,n) printf("%d %d\n",p[i].x,p[i].y);
}
int main(){
	solve();
}

 


Popping Balloons

时间限制:C/C++ 5秒,其他语言10秒
空间限制:C/C++ 524288K,其他语言1048576K
64bit IO Format: %lld

题目描述

Recently, an interesting balloon-popping game can be commonly found near the streets. The rule of this game is quite simple: some balloons are tied to cells of a lattice, and you are allowed to throw some darts to prick the balloons. The more balloons you pierce, the more incredible prize you will get.

Probably because too many people have got bored with this childish game, a new variation of the game has appeared. In this variation, you should prick the balloons by shooting an air rifle instead of throwing darts. You can make six shots in total, three horizontally and three vertically. If you shoot horizontally (vertically, resp.), all balloons in the row (column, resp.) are popped. In order to increase the difficulty, there is one restriction imposed on your shots: the distances between any two adjacent horizontal shots and any two adjacent vertical shots must all equal to a given number $r$. The problem is, what is the maximum number of balloons you can pop by making three horizontal and three vertical shots, under the aforementioned restriction.

输入描述:

The first line of input is two integers n, r (1≤n,r≤105)(1 \leq n, r \leq 10^5)(1≤n,r≤105), the number of balloons and the distance between any two adjacent horizontal or vertical shots.

The remaining part of the input is n lines, specifying the positions of the balloons. Each of these lines contains two integers x, y (0≤x,y≤105)(0 \leq x, y \leq 10^5)(0≤x,y≤105), denoting a balloon positioned at (x, y). Note that multiple balloons may lie in the same position.

输出描述:

Output the answer as a single integer in one line.

示例1

输入

7 1
0 0
1 1
2 2
3 3
4 4
5 5
7 8

输出

6

示例2

输入

5 2
0 10
2 3
5 7
9 6
2 3

输出

4

用f(i)表示中间一枪打第i行,能够射中的气球个数;
用g(i)表示中间一枪打第i列,能射中的气球个数。
用multiset存所有g(i)的值,枚举中间一枪打第x行,将对每一个位于第x-r,x+r行的气球,将它们影响到的列(共三列)的g(j)的值更新,然后更新multiset内的元素。
中间一枪打第x行的最大收益即f(x)+(当前multiset内最大元素)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int seg[100100<<2],sy[300300];int r,n;
inline void write(ll x){
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}
void modi(int pos,int l,int r,int pt,int v){
    if(pt<=0) return;
    if(l>r) return;
    if(l==r) {seg[pos]=v;return;}
    int md=(l+r)>>1;
    if(md>=pt) modi(pos<<1,l,md,pt,v);
    else if(md<pt) modi(pos<<1|1,md+1,r,pt,v);
    seg[pos]=max(seg[pos<<1],seg[pos<<1|1]);
    return;
}
void build(int pos,int l,int r){
    if(l>r) return;
    if(l==r) {seg[pos]=sy[r]+sy[r+::r]+sy[r+::r*2];return;}
    int md=(l+r)>>1;
    build(pos<<1,l,md);
    build(pos<<1|1,md+1,r);
    seg[pos]=max(seg[pos<<1],seg[pos<<1|1]);
    return;
}
int que(){
    return seg[1];
}
int ty[300300];
vector<int> v[300300];
int ans=0;int cnt=0;
void jia(int pt){
    for(int i=0;i<(int)v[pt].size();i++){
        cnt++;
        ty[v[pt][i]]--;
        if(v[pt][i]>0) modi(1,1,100010,v[pt][i],ty[v[pt][i]]+ty[v[pt][i]+r]+ty[v[pt][i]+2*r]);
        if(v[pt][i]-r>0) modi(1,1,100010,v[pt][i]-r,ty[v[pt][i]-r]+ty[v[pt][i]]+ty[v[pt][i]+r]);
        if(v[pt][i]-r*2>0) modi(1,1,100010,v[pt][i]-r*2,ty[v[pt][i]-2*r]+ty[v[pt][i]-r]+ty[v[pt][i]]);
    }
    return;
}
void dell(int pt){
    if(pt<=0) return;
    for(int i=0;i<(int)v[pt].size();i++){
        cnt--;
        ty[v[pt][i]]++;
        if(v[pt][i]>0) modi(1,1,100010,v[pt][i],ty[v[pt][i]]+ty[v[pt][i]+r]+ty[v[pt][i]+2*r]);
        if(v[pt][i]-r>0) modi(1,1,100010,v[pt][i]-r,ty[v[pt][i]-r]+ty[v[pt][i]]+ty[v[pt][i]+r]);
        if(v[pt][i]-r*2>0) modi(1,1,100010,v[pt][i]-r*2,ty[v[pt][i]-2*r]+ty[v[pt][i]-r]+ty[v[pt][i]]);
    }
    return;
}
void gao(){
    cnt=0;
    for(int i=1;i<100010;i++){
        //if(v[i].size()==0) continue;
        int tmp=1;
        cnt=0;
        jia(i);
        if(i>r) jia(i-r),tmp++;
        if(i>2*r) jia(i-2*r),tmp++;
        ans=max(ans,que()+cnt);
        if(tmp>=3){
            dell(i-2*r);
        }
        if(tmp>=2) dell(i-r);
        dell(i);
        assert(cnt==0);
    }
    return;
}
int main() {
    scanf("%d%d",&n,&r);
    for(int i=1;i<=n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        x++;y++;
        v[x].push_back(y);
        sy[y]++;
        ty[y]=sy[y];
    } 
    ans=0;build(1,1,100010);
    gao();
    printf("%d\n",ans);
}

 


Road Construction

时间限制:C/C++ 3秒,其他语言6秒
空间限制:C/C++ 524288K,其他语言1048576K
Special Judge, 64bit IO Format: %lld

题目描述

The mayor of Byteland is planning to build a new road across the town. Constructing new roads may facilitate transportation and stimulate economic development; the negative aspects include, the noise that may affect the residents nearby, and the nonnegligible impacts on the local ecological environment.

You have been required to draft a road construction plan. In your plan, you can model the residents of the town as points, and the road as a straight line of infinite length. Your plan should satisfy the following conditions:
– The road should not pass through any resident of the city;
– The numbers of residents on both sides of the road are equal;
– The minimum of the distances of the residents to the road is maximized.
The following figure depicts the optimal road construction plan for the first sample test data.

Since there are too many residents in Byteland, you believe it is impossible to find such a construction plan manually. It’s your time to write a program and find the optimal plan.

输入描述:

The input starts with a line containing an even integer n (1≤n≤300)(1 \leq n \leq 300)(1≤n≤300) indicating the number of residents in Byteland. It is then followed by n lines, each containing two integers x, y (∣x∣,∣y∣≤106)(|x|, |y| \leq 10^6)(∣x∣,∣y∣≤106), the Cartesian coordinates of a resident. No two residents share the same coordinates.

输出描述:

Print the minimum of the distances of the residents to the road you plan to build. Your answer should have an absolute or relative error of no more than 10−610^{-6}10−6.

示例1

输入

6
0 0
3 0
1 2
4 3
-1 4
5 -3

输出

1.264911064067

示例2

输入

2
1 3
2 5

输出

1.118033988750

最优的直线一定平行或垂直于两个点的连线。
枚举最优直线斜率(最多有n^2个),然后用kth-elment找到以这条直线排序的中间两个点,答案即两个点到该直线的距离差。

#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x;}
const double eps=1e-10;
struct node{
    double x,y;
    double k;
    bool operator < (const node& b){
        return k<b.k;
    }
};
node a[350],b[350];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lf%lf",&a[i].x,&a[i].y);
    }
    double ans=-1;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(fabs(a[i].x-a[j].x)>eps){
                double k=(a[i].y-a[j].y)/(a[i].x-a[j].x);
                for(int pt=1;pt<=n;pt++){
                    b[pt]=a[pt];
                    b[pt].k=-k*b[pt].x+b[pt].y;
                }
                sort(b+1,b+1+n);
                double dis=fabs(b[n/2].k-b[n/2+1].k);
                ans=max(ans,dis/2.0/sqrt(k*k+1));
            }
            else{
                for(int pt=1;pt<=n;pt++){
                    b[pt]=a[pt];
                    b[pt].k=b[pt].x;
                }
                sort(b+1,b+1+n);
                ans=max(ans,fabs(b[n/2].x-b[n/2+1].x)/2.0);
            }
            if(fabs(a[i].y-a[j].y)>eps){
                double k=-(a[i].x-a[j].x)/(a[i].y-a[j].y);
                for(int pt=1;pt<=n;pt++){
                    b[pt]=a[pt];
                    b[pt].k=-k*b[pt].x+b[pt].y;
                }
                sort(b+1,b+1+n);
                double dis=fabs(b[n/2].k-b[n/2+1].k);
                ans=max(ans,dis/2.0/sqrt(k*k+1));
            }
            else{
                for(int pt=1;pt<=n;pt++){
                    b[pt]=a[pt];
                    b[pt].k=b[pt].x;
                }
                sort(b+1,b+1+n);
                ans=max(ans,fabs(b[n/2].x-b[n/2+1].x)/2.0);
            }
        }
    }
    printf("%.12lf\n",ans);
    return 0;
}

 


Stammering Chemists

时间限制:C/C++ 3秒,其他语言6秒
空间限制:C/C++ 524288K,其他语言1048576K
64bit IO Format: %lld

题目描述

Like many other organic chemists, you are busy in synthesizing, separating, purifying and identifying new chemical compounds all year round. Getting bored with traditional substance isolation and identification methods, such as column chromatography, a bold idea comes to your mind: Computer Assisted Molecule Identification (CAMI). With this technology, millions of chemists can be freed from arduous manual labor. How promising!

Currently, you are developing a simplified version of CAMI that works for hydrocarbons (organic compounds consisting of hydrogen and carbon only). All hardware-side technologies are done, and you are just going to write the program. The sensor reports all carbon atoms as well as the chemical bonds between them. This naturally forms a graph, where carbon atoms are vertices, and the bonds are edges. Each connected component of this graph corresponds to a molecule, and the component itself is called hydrogen-depleted molecular graph (HDMG) of the molecule, since we generally do not care about hydrogen atoms.

The sensor has just detected some hexane molecules, which is a specific kind of hydrocarbons, consisting of 6 carbon atoms and 14 hydrogen atoms per molecule. There are five essentially different hexanes, also known as isomers:

Your task is to identify, for each hexane molecule detected, which specific type of hexane isomer it is. A molecule should be identified as any of the above isomers if its hydrogen-depleted molecular graph is isomorphic to the HDMG presented in the above table.

输入描述:

The first line of input consists of only a single integer T (1≤T≤200000)(1 \leq T \leq 200000)(1≤T≤200000), denoting the number of hexane molecules detected.

Every five lines of the remaining part of the input specify a molecule detected. Each of the five lines contains two integers a, b (1≤a,b≤6,a≠b)(1 \leq a, b \leq 6, a \neq b)(1≤a,b≤6,a​=b), denoting a bond between carbon atoms a and b. In each molecule, the carbon atoms are numbered 1 through 6.

It is guaranteed that, for each molecule in the input, it is exactly one type of the hexane isomers listed above.

输出描述:

For each molecule in the input, display the name of the isomer in one line.

示例1

输入

2
1 2
2 3
3 4
4 5
5 6
1 4
2 3
3 4
4 5
5 6

输出

n-hexane
3-methylpentane

签到,对每棵树编码,枚举每个全排列,判断是否完全相同。

#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x;}
int g[10][10];
int in[10],mk[6];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(g,0,sizeof(g));
        memset(in,0,sizeof(in));
        memset(mk,0,sizeof(mk));
        for(int i=1;i<=5;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            g[a][b]=g[b][a]=1;
            in[b]++;in[a]++;
        }
        for(int i=1;i<=6;i++){
            mk[in[i]]++;
        }
        if(mk[4]){
            printf("2,2-dimethylbutane\n");
        }
        else if(mk[3]==2){
            printf("2,3-dimethylbutane\n");
        }
        else if(mk[1]==2){
            printf("n-hexane\n");
        }
        else{
            int pt;
            for(int i=1;i<=6;i++) if(in[i]==3){
                pt=i;
                break;
            }
            int fg=0;
            for(int i=1;i<=6;i++){
                if(g[pt][i]){
                    if(in[i]==1){
                        fg+=1;
                    }
                }
            }
            if(fg==2){
                printf("2-methylpentane\n");
            }
            else printf("3-methylpentane\n");
        }
    }
    return 0;
}

 


Wood Processing

时间限制:C/C++ 3秒,其他语言6秒
空间限制:C/C++ 524288K,其他语言1048576K
64bit IO Format: %lld

题目描述

In the wood industry, it is very common to make big wood boards by combining planks. To combine several planks into boards, the carpenter may cut some of the planks horizontally and discard one of the two parts, such that the heights of all planks are equal. Then, the planks are joined together, forming a big wood board. The height of the board is the common height of the planks, and the width of the board is the sum of the widths of the planks.

However, cutting planks may result in huge wastes. The problem is, given n planks, determine the minimum total wasted area of planks to make k boards from these planks. You may freely reorder and combine these planks. Note that the mechanical properties of a plank are anisotropic, so you can’t rotate the planks. Also, all planks must be used; you cannot discard any whole plank.

输入描述:

The first line of the input contains two integers n, k (1≤n≤5000,1≤k≤2000,k≤n)(1 \leq n \leq 5000, 1 \leq k \leq 2000, k \leq n)(1≤n≤5000,1≤k≤2000,k≤n), denoting the number of planks given and the number of boards to make.

Each of the remaining n lines contains two integers w, h (1≤w,h≤107)(1 \leq w, h \leq 10^7)(1≤w,h≤107), denote the width and the height of a given plank.

输出描述:

Output the minimum wasted area as an integer.

示例1

输入

3 2
3 3
4 7
2 5

输出

4

示例2

输入

6 3
1 1
1 2
1 3
1 4
1 5
1 6

输出

3

每次裁剪的一刀一定是对于高度连续的一段,故先将所有木板按高度从大到小排序。
dp[i]j表示前i刀,割了高度前j高的木板,所浪费的最小代价。
转移有dp[i]j=max_k(dp[i-1][k+sum[j]-sum[k]-height[j]*(lens[j]-lens[k]),其中sum[x]表示前x高的木板的总面积,lens[x]表示前x高的木板的总宽度。考虑到复杂度是n^3的,用斜率优化到n^2

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=5500;
const ll INF=(ll)1e18;
ll q[maxn],dp[2][maxn],pres[maxn],prew[maxn];
int op=0,head,tail;
struct node{
	ll w,h;
	bool operator < (const node &b) const{
        return h < b.h;
    }
}p[5500];
ll getdp(int i,int k) {return dp[op^1][k]+(pres[i]-pres[k+1])-p[k+1].h*(prew[i]-prew[k+1]);}
ll getup(int k1,int k2) {return (dp[op^1][k1]-pres[k1+1]+p[k1+1].h*prew[k1+1])-(dp[op^1][k2]-pres[k2+1]+p[k2+1].h*prew[k2+1]);}
ll getdown(int k1,int k2) {return p[k1+1].h-p[k2+1].h;}
int main(){
	int n,k;scanf("%d%d",&n,&k);
    rep(i,1,n) scanf("%lld%lld",&p[i].w,&p[i].h);
    sort(p+1,p+1+n); op=0;
    rep(i,1,n){
    	pres[i]=pres[i-1]+p[i].w*p[i].h;
    	prew[i]=prew[i-1]+p[i].w;
    	dp[op][i]=INF;
    }
    rep(j,1,k){
    	op^=1;
        head=tail=0;
        q[tail++]=0;
        rep(i,1,n){
            while (head+1<tail && (__int128)getup(q[head+1],q[head])<=prew[i]*(__int128)getdown(q[head+1],q[head])) head++;
            dp[op][i]=getdp(i,q[head]);
            while (head+1<tail && (__int128)getup(i,q[tail-1])*(__int128)getdown(q[tail-1],q[tail-2])<=(__int128)getdown(i,q[tail-1])*(__int128)getup(q[tail-1],q[tail-2])) tail--;
            q[tail++]=i;
        }
    }
    printf("%lld\n",dp[op][n]);
}

 

发表评论,支持MarkDown语法