首页 > 编程札记 > 编程

noip2016 (difficult as HLJOI2016???)

阅读： 评论：0

noip2016 (difficult as HLJOI2016???)

noip2016 (difficult as HLJOI2016???)

D1:

T2:

感觉挺难的但是部分分的提示挺充足

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<cmath>
 7 using namespace std;
 8 template<typename T>
 9 inline void read(T &a){
10     a=0;T b=1;char x=getchar();
11     while(x<'0'||'9'<x){
12         if(x=='-')b=-1;
13         x=getchar();
14     }
15     while('0'<=x&&x<='9'){
16         a=(a<<1)+(a<<3)+x-'0';
17         x=getchar();
18     }
19     a*=b;
20 }
21 char C_[50];
22 int TEMP;
23 template<typename T>
24 inline void write(T a){
25     if(a<0){
26          putchar('-');
27          a=-a;
28     }
29     do{
30          C_[++TEMP]=a%10+'0';
31          a/=10;
32     }while(a);
33     while(TEMP)putchar(C_[TEMP--]);
34 }
35 /*
36 从 u到v 的等差单调路径 有贡献
37 当且仅当路径经过点 i 且路径起点与 i 的距离等于 wi
38 
39 于是差分
40 把u->v <=> u->lca lca->v <=> 
41 u->root(贡献+1) 
42 lca->root(贡献-1) 
43 
44 root->fa[lca](贡献-1) 
45 root->(贡献+1) 
46 */
47 int main()
48 {
49      return 0;
50 }
running

。。。（注意提示）

感觉自己想麻烦了，其实就是找一个好维护的不变量，预处理出来，再O(logn) 以内的复杂度查询

 总结

1.不要痴迷于想正解，先打暴力在想正解，否则就会有时间想没时间写

2.能设计O(n)算法就不要使用数据结构，能省一个logn 的复杂度

3.这种统计类问题往往不能直接一个一个加，而是构造出几个不变量和一个关系式，以此查询及统计贡献

and 条件和贡献之间往往不是等价的、删除的复杂度很高，所以要使用差量法进行统计

4.新思路：全局桶+增量法（由于删除操作很费时间所以我们记录初始时 的总贡献 和结束时的总贡献，将其作差就是这一过程中的贡献）

5.正解往往是各种部分分算法的综合，所以先想部分分在想正解有帮助

安利一个实用知识点--->Tarjan O(n+q)求lca

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<cmath>
 7 using namespace std;
 8 template<typename T>
 9 inline void read(T &a){
10     a=0;T b=1;char x=getchar();
11     while(x<'0'||'9'<x){
12         if(x=='-')b=-1;
13         x=getchar();
14     }
15     while('0'<=x&&x<='9'){
16         a=(a<<1)+(a<<3)+x-'0';
17         x=getchar();
18     }
19     a*=b;
20 }
21 char C_[50];
22 int TEMP;
23 template<typename T>
24 inline void write(T a){
25     if(a<0){
26          putchar('-');
27          a=-a;
28     }
29     do{
30          C_[++TEMP]=a%10+'0';
31          a/=10;
32     }while(a);
33     while(TEMP)putchar(C_[TEMP--]);
34 }
35 const int maxn=5e5+5;
36 int fst[maxn][2],nxt[maxn<<1][2],to[maxn<<1][2],edge_count[2]={1,1},lca[maxn<<1];
37 inline void add(int x,int y,bool b){
38     edge_count[b]++;
39     to[edge_count[b]][b]=y;
40     nxt[edge_count[b]][b]=fst[x][b];
41     fst[x][b]=edge_count[b];
42 }
43 int f[maxn];
44 int find(int x){return f[x]==x ? x : f[x]=find(f[x]) ;}
45 bool vis[maxn];
46 //标记是否找过，找过则对方结点的最上层为lca ，利用了dfs序性质 
47 
48 int n,m,s;
49 void dfs(int u){
50     f[u]=u;//dsu_init
51     vis[u]=1;
52     for(int i=fst[u][0];i;i=nxt[i][0]){
53         int v=to[i][0];
54         if(!vis[v]){
55             dfs(v);
56             f[v]=u;
57         }
58     }
59     for(int i=fst[u][1];i;i=nxt[i][1]){
60         int v=to[i][1];
61         if(vis[v]){
62             lca[i]=lca[i^1]=find(v);
63         }
64     }
65 }
66 int main()
67 {
68     read(n);read(m);read(s);
69     for(int i=1,x,y;i<n;i++){
70         read(x);read(y);
71         add(x,y,0);add(y,x,0);
72     }
73     for(int i=1,x,y;i<=m;i++){
74         read(x);read(y);
75         add(x,y,1);add(y,x,1);
76     }
77     dfs(s);
78     for(int i=1;i<=m;i++)write(lca[i<<1]),putchar('n');
79      return 0;
80 }
Tarjan+dsu 求lca

 

D1:

T1：

注意各种定理的使用条件

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 int t,k;
 6 const int maxn=2e3+5;
 7 /*
 8 由于无法使用 inv的递推公式，并且不能使用CRT
 9 考虑杨辉三角递推（n*m）
10 
11 */
12 int n,m;
13 int c[maxn][maxn],ans[maxn][maxn];
14 int main(){
15     freopen("problem.in","r",stdin);
16     freopen("problem.out","w",stdout);
17     scanf("%d%d",&t,&k);
18     
19     for(int i=0;i<=maxn-5;i++)c[i][0]=1;
20     
21     for(int i=1;i<=maxn-5;i++)for(int j=1;j<=i;j++){
22         c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
23         if(!c[i][j])ans[i][j]++;
24     }
25     /*for(int i=0;i<=20;i++){
26     for(int j=0;j<=i;j++)printf("%d ",c[i][j]);
27     printf("n");
28     }*/
29     
30     
31     for(int i=1;i<=maxn-5;i++)for(int j=1;j<=maxn-5;j++)
32     ans[i][j]+=(ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1]);
33     
34     /*for(int i=0;i<=20;i++){
35     for(int j=0;j<=i;j++)printf("%d ",ans[i][j]);
36     printf("n");
37     }*/
38     for(int i=1;i<=t;i++){
39         scanf("%d%d",&n,&m);
40         printf("%dn",ans[n][m]);
41     }
42     return 0;
43 }
problem

 

T2:

force！！！注意O(nlogn)极限是3e6

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<cmath>
 5 #include<cstdlib>
 6 #include<algorithm>
 7 #include<queue>
 8 #define LL long long
 9 using namespace std;
10 const int maxn=1e5+5;
11 const int maxm=7e6+5;
12 const int INF=1e9;
13 int n,m,q,t,cnt;
14 LL u,v;
15 int num[maxn];
16 inline int getpart(int x){
17     LL ans=u*x/v;
18     return (int )ans;
19 }
20 int que[maxm][3];
21 int f[3]={1,1,1},r[3];
22 int main(){
23     freopen("earthworm.in","r",stdin);
24     freopen("earthworm.out","w",stdout);
25     
26     scanf("%d%d%d%lld%lld%d",&n,&m,&q,&u,&v,&t);
27     for(int i=1;i<=n;i++){
28         scanf("%d",&num[i]);
29     }
30     sort(num+1,num+n+1);
31     for(int i=n;i>=0;i--){
32         que[++r[0]][0]=num[i];
33     }
34     //for(int i=1;i<=n;i++)printf("%d ",que[i][0]);
35     //printf("n");
36 
37     for(int i=1;i<=m;i++){
38         int k=-1,Max=-INF;
39         if(f[0]<=r[0]  && que[f[1]][1]>=Max){
40             Max=que[f[0]][0];
41             k=0;
42         }
43          if(f[1]<=r[1] && que[f[1]][1]>=Max){
44             Max=que[f[1]][1];
45             k=1;
46         }
47          if(f[2]<=r[2] &&que[f[2]][2]>=Max){
48             Max=que[f[2]][2];
49             k=2;
50         }
51         LL ans=Max+cnt;
52         cnt+=q;
53         que[++r[1]][1]=getpart(ans)-cnt;
54         que[++r[2]][2]=ans-getpart(ans)-cnt;
55         f[k]++;
56 
57         if(i%t==0)printf("%d ",ans);
58 
59     }
60     printf("n");
61 
62    /* for(int i=0;i<3;i++){
63     for(int j=f[i];j<=r[i];j++)printf("%d",que[j][i]+cnt);
64     putchar('n');}*/
65 //printf("%dn",r[0]+r[1]+r[2]-f[0]-f[1]-f[2]+3);
66 
67     for(int i=1;i<=n+m;i++){
68         int k=-1,Max=-INF;
69         if(f[0]<=r[0]  && que[f[0]][0]>=Max){
70             Max=que[f[0]][0];
71             k=0;
72         }
73          if(f[1]<=r[1] && que[f[1]][1]>=Max){
74             Max=que[f[1]][1];
75             k=1;
76         }
77          if(f[2]<=r[2] &&que[f[2]][2]>=Max){
78             Max=que[f[2]][2];
79             k=2;
80         }
81      //  printf("%d %dn",k,Max+cnt);
82         if(i%t==0)printf("%d ",Max+cnt);
83         f[k]++;
84     }
85     return 0;
86 }
force

O(nlogn)：

利用好单调性，然后分析分析神奇性质就可以O(n) 进行选择了，

！！！注意开LongLong！！！

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<cmath>
 5 #include<cstdlib>
 6 #include<algorithm>
 7 #include<queue>
 8 #define LL long long
 9 using namespace std;
10 const int maxn=1e5+5;
11 const int maxm=7e6+5;
12 const LL  INF=1ll<<62;
13 int n,m,t;
14 LL u,v,cnt=0ll,q;
15 LL num[maxn];
16 inline LL getpart(LL x){
17     return u*x/v;
18 }
19 LL que[maxm][4];
20 int f[4]={1,1,1,0},r[4]={0,0,0,0};
21 int main(){
22     scanf("%d%d%lld%lld%lld%d",&n,&m,&q,&u,&v,&t);
23     for(int i=1;i<=n;i++){
24         scanf("%lld",&num[i]);
25     }
26     sort(num+1,num+n+1);
27   /*  for(int i=1;i<=n;i++)printf("%d ",num[i]);
28     printf("n");*/
29     for(int i=n;i;i--){
30         que[++r[0]][0]=num[i];
31     }
32    /*for(int i=1;i<=n;i++)printf("%d ",que[i][0]);
33     printf("n");*/
34 
35     for(int i=1;i<=m;i++){
36         int k=-1;
37         LL Max=-INF;
38         if(f[0]<=r[0]  && que[f[0]][0]>=Max){
39             Max=que[f[0]][0];
40             k=0;
41         }
42          if(f[1]<=r[1] && que[f[1]][1]>=Max){
43             Max=que[f[1]][1];
44             k=1;
45         }
46          if(f[2]<=r[2] &&que[f[2]][2]>=Max){
47             Max=que[f[2]][2];
48             k=2;
49         }
50         LL ans=cnt+Max;//cout<<ans<<endl;
51         cnt+=q;
52         que[++r[1]][1]=getpart(ans)-cnt;
53         que[++r[2]][2]=ans-getpart(ans)-cnt;
54         f[k]++;
55 
56         if(i%t==0)printf("%lld ",ans);
57 
58     }
59     printf("n");
60 
61    /* for(int i=0;i<3;i++){
62     for(int j=f[i];j<=r[i];j++)printf("%d",que[j][i]+cnt);
63     putchar('n');}*/
64 //printf("%dn",r[0]+r[1]+r[2]-f[0]-f[1]-f[2]+3);
65 
66     for(int i=1;i<=n+m;i++){
67         int k=-1;
68         LL Max=-INF;
69         if(f[0]<=r[0]  && que[f[0]][0]>=Max){
70             Max=que[f[0]][0];
71             k=0;
72         }
73          if(f[1]<=r[1] && que[f[1]][1]>=Max){
74             Max=que[f[1]][1];
75             k=1;
76         }
77          if(f[2]<=r[2] &&que[f[2]][2]>=Max){
78             Max=que[f[2]][2];
79             k=2;
80         }
81         f[k]++;
82      //  printf("%d %dn",k,Max+cnt);
83         if(i%t==0)printf("%lld ",cnt+Max);
84     }
85     return 0;
86 }
earthworm

T3:

 本题想到了正解但是考场上没有调试对（不要在最后的时候还在写代码，暴力优先[感谢Duan2baka 大佬的真心劝告]，555）

wa：

带入公式错了

没有被某一条抛物线覆盖的时候记得在加一只鸟

去重

最后浮点数的精度问题，最高是3次项所以判断是否为0应该比较是否< 1e-6

  1 #include<cstdio>
  2 #include<cmath>
  3 #include<cstring>
  4 #include<map>
  5 #include<ctime>
  6 #include<cstdlib>
  7 #define LL long long
  8 #define DB double
  9 using namespace std;
 10 /*
 11 状压Dp
 12 
 13 */
 14 int p;
 15 struct bird{
 16     DB a,b;int cnt;
 17     bird(DB A=0.0,DB B=0.0,int C=0):a(A),b(B),cnt(C){}
 18     const bool operator ==(const bird & xx)const{
 19         return abs(b/xx.b-a/xx.a)<0.01;
 20     }
 21 }b[500];
 22 int finish[(1<<18)+5];
 23 struct Node{
 24     DB x,y;
 25     
 26     inline bool okbird(const bird &k){
 27         return abs(k.a*x*x+k.b*x-y)<0.01;
 28     }
 29     
 30 }a[20];
 31 inline bool judge(Node a1,Node a2){
 32     DB x=a1.x-a2.x;
 33     DB y=a1.y/a1.x-a2.y/a2.x;
 34     if(abs(y)<0.01 || abs(x)<0.01 || x*y>0)return 0;//无解 或者 无数解 或者 a>0
 35     return 1;
 36 }
 37 inline bird get_ans(Node a1,Node a2){
 38     DB x=a1.x-a2.x;
 39     DB y=a1.y/a1.x-a2.y/a2.x;
 40     DB ansa=y/x;
 41     DB ansb=a1.y/a1.x-ansa*a1.x;
 42     return bird(ansa,ansb);
 43 }
 44 inline int read(){
 45     int a=0;char x=getchar();
 46     while(x<'0'||'9'<x)x=getchar();
 47     while('0'<=x && x<='9'){
 48         a=(a<<1)+(a<<3)+x-'0';
 49         x=getchar();
 50     }
 51     return a;
 52 }
 53 int t,n,m;
 54 int f[(1<<18)+5];
 55 bool gunk[20];
 56 
 57 int main(){
 58     //freopen("angrybirds.in","r",stdin);
 59     //freopen("angrybirds.out","w",stdout);
 60     t=read();
 61     for(int T=1;T<=t;T++){
 62         n=read();m=read();
 63         
 64         memset(gunk,0,sizeof(gunk));
 65         //memset(finish,0,sizeof(finish));
 66         for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);
 67         //if(n==2){printf(judge(a[1],a[2]) ? "1n" : "2n" );continue;}
 68         
 69         p=0;
 70         for(int i=1;i<n;i++)
 71             for(int j=i+1;j<=n;j++)
 72             //printf("i%d j%d:",i,j);
 73             //printf("%dn",judge(a[i],a[j]));
 74             
 75                 if(judge(a[i],a[j])){
 76                 b[p]=get_ans(a[i],a[j]);
 77                 
 78                 for(int k=1;k<=n;k++){
 79                     //printf("%d %d ",k,a[k].okbird(b[p]));
 80                     if(a[k].okbird(b[p]))b[p]t|=(1<<(k-1)),gunk[k]=1;
 81                 }
 82             //printf("%d",b[p]t);
 83             
 84             if(finish[b[p]t]!=T){
 85                     finish[b[p]t]=T;
 86                     p++;
 87                 }
 88             }
 89         
 90         for(int i=1;i<=n;i++)if(!gunk[i])b[p++]t=1<<(i-1);
 91         
 92         memset(f,0x3f,sizeof(f));
 93         f[0]=0;
 94         for(int s=0;s<(1<<n);s++){
 95             for(int k=0;k<p;k++)f[s|b[k]t]=min(f[s|b[k]t],f[s]+1);
 96         }
 97         printf("%dn",f[(1<<n)-1]);
 98     }
 99     return 0;
100 }
101 /*
102 1
103 2 0
104 1.00 3.00
105 3.00 3.00
106 */
angrybirds

 ac:

  1 #include<cstdio>
  2 #include<cmath>
  3 #include<cstring>
  4 #include<map>
  5 #include<ctime>
  6 #include<cstdlib>
  7 #define LL long long
  8 #define DB double
  9 using namespace std;
 10 /*
 11 状压Dp
 12 
 13 */
 14 const double lit=1e-6;
 15  
 16 int p;
 17 struct bird{
 18     DB a,b;int cnt;
 19     bird(DB A=0.0,DB B=0.0,int C=0):a(A),b(B),cnt(C){}
 20     const bool operator ==(const bird & xx)const{
 21         return abs(b/xx.b-a/xx.a)<lit;
 22     }
 23 }b[500];
 24 int finish[(1<<18)+5];
 25 struct Node{
 26     DB x,y;
 27     
 28     inline bool okbird(const bird &k){
 29         return abs(k.a*x*x+k.b*x-y)<lit;
 30     }
 31     
 32 }a[20];
 33 inline bool judge(Node a1,Node a2){
 34     DB x=a1.x-a2.x;
 35     DB y=a1.y/a1.x-a2.y/a2.x;
 36     if(abs(y)<lit || abs(x)<lit || x*y>0)return 0;//无解 或者 无数解 或者 a>0
 37     return 1;
 38 }
 39 inline bird get_ans(Node a1,Node a2){
 40     DB x=a1.x-a2.x;
 41     DB y=a1.y/a1.x-a2.y/a2.x;
 42     DB ansa=y/x;
 43     DB ansb=a1.y/a1.x-ansa*a1.x;
 44     return bird(ansa,ansb);
 45 }
 46 inline int read(){
 47     int a=0;char x=getchar();
 48     while(x<'0'||'9'<x)x=getchar();
 49     while('0'<=x && x<='9'){
 50         a=(a<<1)+(a<<3)+x-'0';
 51         x=getchar();
 52     }
 53     return a;
 54 }
 55 int t,n,m;
 56 int f[(1<<18)+5];
 57 bool gunk[20];
 58 
 59 int main(){
 60     //freopen("angrybirds.in","r",stdin);
 61     //freopen("angrybirds.out","w",stdout);
 62     t=read();
 63     for(int T=1;T<=t;T++){
 64         n=read();m=read();
 65         
 66         memset(gunk,0,sizeof(gunk));
 67         //memset(finish,0,sizeof(finish));
 68         for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);
 69         //if(n==2){printf(judge(a[1],a[2]) ? "1n" : "2n" );continue;}
 70         //for(int i=1;i<=n;i++)printf("%lf %lfn",a[i].x,a[i].y); 
 71         p=0;
 72         for(int i=1;i<n;i++)
 73             for(int j=i+1;j<=n;j++)
 74             //printf("i%d j%d:",i,j);
 75             //printf("%dn",judge(a[i],a[j]));
 76             
 77                 if(judge(a[i],a[j])){
 78                 b[p]=get_ans(a[i],a[j]);
 79                 
 80                 for(int k=1;k<=n;k++){
 81                     //printf("%d %d ",k,a[k].okbird(b[p]));
 82                     if(a[k].okbird(b[p]))b[p]t|=(1<<(k-1)),gunk[k]=1;
 83                 }
 84             //printf("%d",b[p]t);
 85             
 86             if(finish[b[p]t]!=T){
 87                     finish[b[p]t]=T;
 88                     p++;
 89                 }
 90             }
 91         
 92         for(int i=1;i<=n;i++)if(!gunk[i])b[p++]t=1<<(i-1);
 93         
 94         memset(f,0x3f,sizeof(f));
 95         f[0]=0;
 96         for(int s=0;s<(1<<n);s++){
 97             for(int k=0;k<p;k++)f[s|b[k]t]=min(f[s|b[k]t],f[s]+1);
 98         }
 99         printf("%dn",f[(1<<n)-1]);
100     }
101     return 0;
102 }
103 /*
104 1
105 2 0
106 1.00 3.00
107 3.00 3.00
108 */
angrybirds

 ！！！但是数据强的话还是不行，于是就产生了O(T*n*2^n）的正解！！！

摘抄自某位dalao的blog

在此发一篇严格 O(Tn2^n) 的完全严谨正解。

设计dp状态：

nle 18n≤18？不是暴搜就是状压。

dp[S]dp[S] 表示已经死了的猪的集合状态为 SS 时最少要发射的鸟数。

明显有

  • dp[0]=0
  • dp[S|line[i][j]]=dp[S∣line[i][j]]=min(dp[S]+1)
  • dp[S|(1<<(i-1)]=dp[S∣(1<<(i−1)]=min(dp[S]+1)

其中 line[i][j] 表示经过 i,j 两点的抛物线能经过的所有点的集合。

这就是网上大多流传的 O(Tn^2*2^n) 算法。优化？

优化1：

发现当 i∈S 或者 j∈S 时没有必要转移。

证明：

  • 若这条线只经过至多三个点，因为其中一个点已被打到，所以可以通过另外两个点的状态转移。如果 i,j 都被打到，则可以通过转移3（单独一个点）转移。
  • 若这条线经过多于三个点，则可以通过其它任选两个点转移。

但是这只能算是常数优化。

优化2：

若令 x为满足 S&(1<<(x-1))=0的最小正整数，则由 S 扩展的转移的所有线都要经过 x。

为什么？这个是对的吗？不经过 x 就会慢吗？

你想一想，先打 1,4，再打 2,3，和先打 2,3，再打 1,4 是不是一样的？

如果这一次转移不打 x，那以后还要再回过头来打 x。这就是多余的转移。

因为经过 x 的线数量是 n，所以每次转移涉及到的线就从 n^2 变成了 n。

只要预处理一下 0-2^18的对应的 x 就能做到 O(Tn*2^n) 了，这才是考场的正解。

似乎比暴搜还快一点~

code:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const double eps=1e-8;
 4 int t,n,m,lines[20][20],lowunbit[1<<20],dp[1<<20];  //lowunbit就是题解中的x
 5 double x[20],y[20];
 6 void equation(double &x,double &y,double a1,double b1,double c1,double a2,double b2,double c2){ //解方程
 7     y=(a1*c2-a2*c1)/(a1*b2-a2*b1);
 8     x=(c1-b1*y)/a1;
 9 }
10 int main(){
11     for(int i=0;i<(1<<18);i++){ //预处理lowunbit
12         int j=1;
13         for(;j<=18 && i&(1<<(j-1));j++);
14         lowunbit[i]=j;
15     }
16     scanf("%d",&t);
17     while(t--){
18         memset(lines,0,sizeof(lines));  //各种初始化
19         memset(dp,0x3f,sizeof(dp));
20         dp[0]=0;
21         scanf("%d%d",&n,&m);
22         for(int i=1;i<=n;i++) scanf("%lf%lf",x+i,y+i);
23         for(int i=1;i<=n;i++)
24             for(int j=1;j<=n;j++){  //处理所有抛物线
25                 if(fabs(x[i]-x[j])<eps) continue;   //x坐标相同，不可能有解
26                 double a,b;
27                 equation(a,b,x[i]*x[i],x[i],y[i],x[j]*x[j],x[j],y[j]);
28                 if(a>-eps) continue;    //解出a和b
29                 for(int k=1;k<=n;k++)
30                     if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<eps) lines[i][j]|=(1<<(k-1));
31             }
32         for(int i=0;i<(1<<n);i++){  //重点！状压开始！
33             int j=lowunbit[i];  //必须经过lowunbit这个点
34             dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1); //单独转移
35             for(int k=1;k<=n;k++) dp[i|lines[j][k]]=min(dp[i|lines[j][k]],dp[i]+1); //所有经过lowunbit的抛物线
36         }
37         printf("%dn",dp[(1<<n)-1]);    //答案
38     }
39 }
amazing Code

summarize:

1.关键还是无用状态的简化与省略

2.利用好题里的限制条件 & 联想之前做过的题目（D2T2）

3.不要因为D1发挥不好而影响D2，难题都会有，暴力分打满就可以了

4.不要沉迷于想正解，往往想完了没时间打

5.学会这种枚举的方式，往往一些题目会用的上

qzh亲传linux调试神器（检查数组越界 & 爆int 等）

-ftrapv -fsanitize=address

 

转载于:.html

本文发布于:2024-01-31 17:08:28，感谢您对本站的认可！

本文链接：https://www.4u4v.net/it/170669211030077.html

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。

上一篇：Python字符串常用方法
下一篇：每天一个Linux命令
标签：difficult
留言与评论（共有 0 条评论）
   
验证码：
推荐文章
排行榜
热门标签

Copyright ©2019-2022 Comsenz Inc.Powered by ©

网站地图1 网站地图2 网站地图3 网站地图4 网站地图5 网站地图6 网站地图7 网站地图8 网站地图9 网站地图10 网站地图11 网站地图12 网站地图13 网站地图14 网站地图15 网站地图16 网站地图17 网站地图18 网站地图19 网站地图20 网站地图21 网站地图22/a> 网站地图23