NOIP2016D2

原题网址：https://www.luogu.org/problem/lists?name=&orderitem=pid&tag=83%7C33

简单的离线

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<algorithm>
 7 using namespace std;
 8 int c[2001][2001]={0},f[2001][2001]={0};
 9 inline int read()
10 {
11     char ch=getchar();
12     int a=0,t=1;
13     while(ch<'0'||ch>'9') {if(ch=='-') t=-1;ch=getchar();}
14     while(ch<='9'&&ch>='0') {a=a*10+ch-'0';ch=getchar();}
15     return a*t;
16 }
17 inline void write(int k){
18     if (k<0) {
19         putchar('-');
20         k=-k;
21     }
22     if (k>9) write(k/10);
23     putchar(k%10+'0');
24 }
25 int main(){
26     //freopen("problem.in","r",stdin); freopen("problem.out","w",stdout);
27     int t=read(),k=read();
28     for (int i=0;i<=2000;i++) c[i][0]=1,c[i][1]=i%k;
29     for (int i=2;i<=2000;i++){
30         for (int j=2;j<=i;j++)
31             c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
32     }
33     
34     /*for (int i=1;i<=5;i++){
35         for (int j=1;j<=i;j++)
36             printf("%d ",c[i][j]);
37         printf("
");
38     }*/
39     
40     for (int i=1;i<=2000;i++){
41         for (int j=1;j<=i;j++){
42             f[i][j]=0;
43             if (c[i][j]==0) f[i][j]=1;
44             if (i!=j) f[i][j]=f[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1];
45             else f[i][j]=f[i][j]+f[i][j-1];
46         }
47     }
48     /*for (int i=1;i<=3;i++){
49         for (int j=1;j<=i;j++)
50             printf("%d ",f[i][j]);
51         printf("
");
52     }*/
53     
54     for (int i=1;i<=t;i++){
55         int n=read(),m=read();
56         if (n<m) m=n;
57         printf("%d
",f[n][m]);
58     }
59     return 0;
60 }

个人感觉优先队列更优

 1 #include <iostream>
 2 #include <queue>
 3 #include <map>
 4 #include <ctime>
 5 #include <cmath>
 6 #include <cstdlib>
 7 #include <cstdio>
 8 #include <cstring>
 9 #include <string>
10 #include <algorithm>
11 #include <iomanip>
12 #include <bitset>
13 #include <set>
14 using namespace std;
15 #define ll long long
16 #define up(i,j,n)       for(int i=j;i<=n;i++)
17 #define down(i,j,n)     for(int i=j;i>=n;i--)
18 #define cmax(a,b)       a=max(a,b)
19 #define cmin(a,b)       a=min(a,b)
20 #define FILE "earthworm"
21 const ll MAXN=1e7+5;
22 const ll oo=1LL<<55;
23 inline ll read(){
24     char ch=getchar();ll x=0,f=1;
25     while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
26     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
27     return x*f;
28 }
29 ll N,M,Q,U,V,T,_old[MAXN],_short[MAXN],_long[MAXN],t1=0,t2=1,t3=1,top2=0,top3=0,cnt=0,delta=0;
30 
31     void init(){
32         N=read();M=read();Q=read();U=read();V=read();T=read();
33         up(i,1,N)_old[++t1]=read();
34         sort(_old+1,_old+t1+1);
35         _old[0]=_short[0]=_long[0]=-oo;
36     }
37     void slove(){
38         while(M--){
39             ll now=max(_old[t1],max(_short[t2],_long[t3]));
40             if(now==_old[t1])t1--;
41             else if(now==_short[t2])t2++;
42             else if(now==_long[t3])t3++;
43             now+=delta;
44             if(!(++cnt%T))printf("%d ",now);
45             ll __short=now*U/V,__long=now-__short;
46             delta+=Q;
47             _short[++top2]=__short-delta;_long[++top3]=__long-delta;
48         }
49         cnt=0;puts("");
50         M=t1+top2+top3-t2-t3+2;
51         while(M--){
52             ll now=max(_old[t1],max(_short[t2],_long[t3]));
53             if(now==_old[t1]&&t1>0)t1--;
54             else if(now==_short[t2]&&t2<=top2)t2++;
55             else if(now==_long[t3]&&t3<=top3)t3++;
56             if(t2>top2)_short[t2]=-oo;
57             if(t3>top3)_long[t3]=-oo;
58             if(!(++cnt%T))printf("%lld ",now+delta);   
59         }
60     }
61 int main(){
62     //freopen(FILE".in","r",stdin);
63     //freopen(FILE".out","w",stdout);
64     init();
65     slove();
66     return 0;
67 }

状压DP不解释

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 int n,l,dp[1<<19],vd[19][19],tp[19];
 8 struct quad
 9 {
10     double a,b;
11     quad() {}
12     quad(double _a,double _b):
13     a(_a),b(_b) {}
14 };
15 double pigx[19],pigy[19];
16 const double eps=1e-10,INF=1e20;
17 inline quad qd(double x1,double y1,double x2,double y2)
18 {
19     if(abs(x1-x2)<eps) return quad(INF,INF);
20     double a=(y1*x2-x1*y2)/(x1*x1*x2-x2*x2*x1),
21     b=(y1-a*x1*x1)/x1;
22     if(a>eps || abs(a)<eps) return quad(INF,INF);
23     return quad(a,b);
24 }
25 inline void cyx()
26 {
27     int i,j,state;dp[0]=0;
28     for(state=1;state<(1<<n);state++)
29     {
30         int res=n+100;l=0;
31         for(i=1;i<=n;i++)
32             if((state>>i-1)%2==1)
33                 tp[++l]=i;
34         for(i=1;i<l;i++)
35             for(j=i+1;j<=l;j++)
36             {
37                 if(vd[tp[i]][tp[j]]==-1) continue;
38                 res=min(res,dp[state&vd[tp[i]][tp[j]]]+1);
39             }
40         for(i=1;i<=l;i++)
41             res=min(res,dp[state-(1<<tp[i]-1)]+1);
42         dp[state]=res;
43     }
44 }
45 inline void work()
46 {
47     int i,j,k;
48     scanf("%d%*d",&n);
49     memset(dp,-1,sizeof(dp));
50     for(i=1;i<=n;i++) for(j=1;j<=n;j++) vd[i][j]=(1<<n)-1;
51     for(i=1;i<=n;i++) scanf("%lf%lf",&pigx[i],&pigy[i]);
52     for(i=1;i<n;i++)
53         for(j=i+1;j<=n;j++)
54         {
55             quad x=qd(pigx[i],pigy[i],pigx[j],pigy[j]);
56             if(abs(x.a-INF)>eps && abs(x.b-INF)>eps)
57                 for(k=1;k<=n;k++)
58                 {
59                     if(abs(x.a*pigx[k]*pigx[k]
60                         +x.b*pigx[k]-pigy[k])<eps)
61                     vd[i][j]-=1<<k-1,vd[j][i]-=1<<k-1;
62                 }
63             else vd[i][j]=vd[j][i]=-1;
64         }
65     cyx();printf("%d
",dp[(1<<n)-1]);
66 }
67 int main()
68 {
69     int T;
70     scanf("%d",&T);
71     while(T--) work();
72     return 0;
73 }