[关闭]
@happyforever 2018-10-31T11:21:21.000000Z 字数 12674 阅读 544

10.27晚上解题报告

解题报告 清北学堂

各题状况

期望得分：
实际得分：

今天撞题了，所以又加了一道附加题

题目及考场代码

T1

图片.png

  1. /*
  2.  */
  3. #include <cstdio>
  4. #include <cstring>
  6. const int N=100005;
  7. char s[N];
  8. int a[N];
  9. /*
  10. void dfs(int now)
  11. {
  12.     long long emp=sum[now-1];
  13.     for(;s[now] && sum[now]-emp<=x;++now);
  14. //      printf("%d ",sum[now]);
  15.     if(!s[now])
  16.     {
  17.         if(sum[now-1]-emp==x)
  18.             flag=true;
  19.         return ;
  20.     }
  21. //  puts("");
  22.     if(sum[now-1]-emp==x)
  23.         dfs(now);
  24. }
  25. */
  26. /*
  27. void bfs(int now)
  28. {
  29.     long long emp;
  30.     while(true)
  31.     {
  32.         emp=sum[now-1];
  33.         for(;s[now] && sum[now]-emp<=x;++now);
  34.         if(!s[now])
  35.         {
  36.             if(sum[now-1]-emp==x)
  37.                 flag=true;
  38.             return ;
  39.         }
  40.         if(sum[now-1]-emp!=x)
  41.             return ;
  42.     }
  43. }
  44. */
  46. int main()
  47. {
  48.     freopen("divide.in","r",stdin);
  49.     freopen("divide.out","w",stdout);
  51.     int T,len;scanf("%d",&T);
  52.     while(T--)
  53.     {
  54.         scanf("%s",s);
  55.         len=strlen(s+1);
  56.         long long sum=0;
  57.         bool flag=false;
  58.         for(int i=0;i<len;++i)
  59.             a[i+1]=s[i]-'0',sum+=a[i+1];
  60.         for(int i=2;i<=len;++i)
  61.         {
  62.             int tom=0,t=0,p;
  63.             if(sum%i==0)
  64.             {
  65.                 p=sum/i;
  66.                 for(int j=1;j<=len;++j)
  67.                 {
  68.                     if(tom+a[j]<p)
  69.                     {
  70.                         tom+=a[j];
  71.                         continue;
  72.                     }
  73.                     else
  74.                         if(tom+a[j]==p)
  75.                         {
  76.                             tom=0;
  77.                             ++t;
  78.                             continue;
  79.                         }
  80.                         else
  81.                             if(tom+a[j]>p)
  82.                                 break;
  83.                 }
  84.                 if(tom==0&&t==i)
  85.                 {
  86.                     flag=true;
  87.                     break;
  88.                 }
  89.             }
  90.         }
  91.         puts(flag?"YES":"NO");
  92.     }
  94.     fclose(stdin);fclose(stdout);
  95.     return 0;
  96. }

T2

图片.png

  1. #include<cstdio>
  2. int n;
  3. const int ans[]={0,1,1,4,38,728,26704,1866256,251548592,412163774,158488195,768116971,789817415};
  5. int main()
  6. {
  7.     freopen("count.in","r",stdin);
  8.     freopen("count.out","w",stdout);
  10.     scanf("%d",&n);
  11.     if(n<=9)
  12.         printf("%d",ans[n]);
  13.     else    printf("baka!\nbzoj 3456 chengshiguihua");
  15.     fclose(stdin); fclose(stdout);
  16.     return 0;
  17. }

T3

图片.png
图片.png

  1. #include <iostream>
  2. #include <cstring>
  3. #include <cstdio>
  5. const int M=100005;
  7. long long ans;
  8. int n,m,tot;
  9. int x[M],y[M],c[M],num[M];
  10. int to[M*2],net[M*2],head[M];
  11. int top[M],size[M],dad[M],deep[M],length[M];
  13. inline int read()
  14. {
  15.     int n=0,w=1;register char c=getchar();
  16.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  17.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  18.     return n*w;
  19. }
  21. void add(int v,int u)
  22. {
  23.     to[++tot]=v;net[tot]=head[u];head[u]=tot;//cap[tot]=w;
  24.     to[++tot]=u;net[tot]=head[v];head[v]=tot;//cap[tot]=w;
  25. }
  26. inline int max(int x,int y)
  27. {return x>y?x:y;}
  29. void dfs(int now)
  30. {
  31.     size[now]=1;
  32.     deep[now]=deep[dad[now]]+1;
  33.     for(int i=head[now];i;i=net[i])
  34.         if(to[i]!=dad[now])
  35.         {
  36.             dad[to[i]]=now;
  37.             length[to[i]]=length[now]+c[to[i]];
  38.             dfs(to[i]);
  39.             size[now]+=size[to[i]];
  40.         }
  41. }
  43. void dfsl(int now)
  44. {
  45.     int t=0;
  46.     if(!top[now])top[now]=now;
  47.     for(int i=head[now];i;i=net[i])
  48.         if(to[i]!=dad[now] && size[to[i]]>size[t])
  49.             t=to[i];
  50.     if(t)
  51.     {
  52.         top[t]=top[now];
  53.         dfsl(t);
  54.     }
  55.     for(int i=head[now];i;i=net[i])
  56.         if(to[i]!=dad[now] && t!=to[i])
  57.             dfsl(to[i]);
  58. }
  60. int lca(int x,int y)
  61. {
  62.     while(top[x]!=top[y])
  63.     {
  64.         if(deep[top[x]]<deep[top[y]])
  65.             std::swap(x,y);
  66.         x=dad[top[x]];
  67.     }
  68.     return deep[x]>deep[y]?y:x;
  69. }
  71. bool judge(int qwq)
  72. {
  73.     for(int i=1;i<=qwq;++i)
  74.         for(int j=i+1;j<=qwq;++j)
  75.         {
  76.             int a=x[i],b=y[i],c=x[j],d=y[j];
  77.             int S=lca(a,b);
  78.             int T=lca(c,d);
  79.             if(deep[S]<deep[T])
  80.             {
  81.                 std::swap(S,T);
  82.                 std::swap(a,c);
  83.                 std::swap(b,d);
  84.             }
  85.             if(lca(S,c)==S||lca(S,d)==S)
  86.                 return false;
  87.         }
  88.     return true;
  89. }
  91. void dfsans(int now,int qwq)
  92. {
  93.     if(now>m)
  94.     {
  95.         long long sum=0;
  96.         if(qwq==1)
  97.         {
  98.             int tmp=lca(x[num[1]],y[num[1]]);
  99.             sum+=length[x[num[1]]]+length[y[num[1]]]-2*length[tmp]+c[tmp];
  100.             ans=max(ans,sum);
  101.         }
  102.         else
  103.             if(qwq>1 && judge(qwq))
  104.             {
  105.                 for(int i=1;i<=qwq;++i)
  106.                     sum+=length[x[i]]+length[y[i]]-2*length[lca(x[i],y[i])]+c[lca(x[i],y[i])];
  107.                 ans=max(ans,sum);
  108.             }
  109.         return ;
  110.     }
  111.     num[qwq+1]=now;
  112.     dfsans(now+1,qwq+1);
  113.     num[qwq+1]=0;
  114.     dfsans(now+1,qwq);
  115. }
  117. int main()
  118. {
  119.     freopen("max.in","r",stdin);
  120.     freopen("max.out","w",stdout);
  122.     scanf("%d",&n);
  123.     for(int i=1;i<=n;++i)
  124.         scanf("%d",&c[i]);
  125.     for(int i=1;i<n;++i)
  126.         add(read(),read());
  127.     length[1]=c[1];
  128.     dfs(1);dfsl(1);
  129.     scanf("%d",&m);
  130.     for(int i=1;i<=m;++i)
  131.         scanf("%d%d",&x[i],&y[i]);
  132.     dfsans(1,0);
  133.     printf("%d",ans);
  135.     fclose(stdin);fclose(stdout);
  136.     return 0;
  137. }

T4

图片.png

  1. /*
  2.  */
  3. #include <cstdio>
  5. const int N=33;
  6. int n,m,a[N],b[N],ans;
  7. inline int max(int x,int y)
  8. {return x>y?x:y;}
  10. void dfs(int now,int sum,int tot)
  11. {
  12.     if(tot<=m)
  13.         ans=max(ans,sum);
  14.     if(now>n)return ;
  15.     dfs(now+1,sum,tot);
  16.     dfs(now+1,sum+b[now],tot^a[now]);
  17. }
  19. int main()
  20. {
  21.     freopen("xor.in","r",stdin);
  22.     freopen("xor.out","w",stdout);
  24.     scanf("%d%d",&n,&m);
  25.     for(int i=1;i<=n;++i)
  26.         scanf("%d%d",&a[i],&b[i]);
  27.     dfs(1,0,0);
  28.     printf("%d",ans);
  30.     fclose(stdin);fclose(stdout);
  31.     return 0;
  32. }

正解及代码

T1

枚举将整个串分成几个部分，而后就可以求出每个部分的总和是多少（也就是划分成的每个部分的“相等”的和是多少），维护前缀和检查和的倍数是否出现。可以开bool数组，查询。

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<string>
  6. #include<cmath>
  7. #include<cstdlib>
  8. #include<ctime>
  9. using namespace std;
  10. typedef long long ll;
  11. typedef long double ld;
  12. typedef pair<int,int> pr;
  13. const double pi=acos(-1);
  14. #define rep(i,a,n) for(int i=a;i<=n;i++)
  15. #define per(i,n,a) for(int i=n;i>=a;i--)
  16. #define Rep(i,u) for(int i=head[u];i;i=Next[i])
  17. #define clr(a) memset(a,0,sizeof a)
  18. #define pb push_back
  19. #define mp make_pair
  20. ld eps=1e-9;
  21. ll pp=1000000007;
  22. ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
  23. ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
  24. ll read(){
  25.     ll ans=0;
  26.     char last=' ',ch=getchar();
  27.     while(ch<'0' || ch>'9')last=ch,ch=getchar();
  28.     while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
  29.     if(last=='-')ans=-ans;
  30.     return ans;
  31. }
  32. //head
  33. #define N 110000
  34. char str[N];
  35. bool a[N*9];
  36. int main(){
  37.     freopen("divide.in","r",stdin);
  38.     freopen("divide.out","w",stdout);
  39.     int T=read();
  40.     while(T--){
  41.         scanf("%s",str);
  42.         int n=strlen(str);
  43.         rep(i,0,9*n)a[i]=0;
  44.         int t=0;a[t]=1;
  45.         rep(i,0,n-1){
  46.             t+=str[i]-'0';
  47.             a[t]=1;
  48.         }
  49.         if(t==0){
  50.             puts("YES");
  51.             continue;
  52.         }
  53.         bool ans=0;
  54.         rep(i,2,n)
  55.             if(t%i==0){
  56.                 int pf=1;
  57.                 int siz=t/i;
  58.                 for(int j=siz;j<=t;j+=siz)
  59.                     if(!a[j]){
  60.                         pf=0;
  61.                         break;
  62.                     }
  63.                 if(pf){
  64.                     ans=1;
  65.                     break;
  66.                 }
  67.             }
  68.         if(ans)puts("YES");
  69.         else puts("NO");
  70.     }
  71.     return 0;
  72. }

T2

都可以通过打表解决
的部分分可以选择表示有个点的图的合法的方案数有多少。枚举所在的联通块的大小，找剩余的点，就是一个不合法的情况。总数是

分算法则是。。。
这也就是为啥会有的部分分，最后分纯粹是为了让某些同学装用的

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<cstdlib>
  7. using namespace std;
  8. typedef long long ll;
  9. typedef long double ld;
  10. typedef pair<int,int> pr;
  11. const double pi=acos(-1);
  12. #define rep(i,a,n) for(int i=a;i<=n;i++)
  13. #define per(i,n,a) for(int i=n;i>=a;i--)
  14. #define Rep(i,u) for(int i=head[u];i;i=Next[i])
  15. #define clr(a) memset(a,0,sizeof a)
  16. #define pb push_back
  17. #define mp make_pair
  18. ld eps=1e-9;
  19. ll pp=998244353;
  20. ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
  21. ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
  22. ll read(){
  23.     ll ans=0;
  24.     char last=' ',ch=getchar();
  25.     while(ch<'0' || ch>'9')last=ch,ch=getchar();
  26.     while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
  27.     if(last=='-')ans=-ans;
  28.     return ans;
  29. }
  30. //head
  31. #define N 310000
  32. ll f[N],b1[N],b2[N],inv[N],f2[N],b[N],tt[N],e[N],recf[N],recb[N],Sum[N];
  33. int bel[N];
  34. int n;
  35. ll C(int n,int m){
  36.     if(n<m)return 0;
  37.     if(m==0 || n==m)return 1;
  38.     return b[n]*inv[n-m]%pp*inv[m]%pp;
  39. }
  40. void fnt(ll *a,int n,int fl){
  41.      for(int i=n>>1,j=1;j<n;j++){
  42.        if(i<j)swap(a[i],a[j]);
  43.        int k=n>>1;
  44.        for(;k&i;i^=k,k>>=1);
  45.         i^=k;
  46.      }
  47.      ll g=powmod(3,(pp-1)/n,pp);
  48.      if(fl==-1)g=powmod(g,n-1,pp);
  49.      e[0]=1;
  50.      for(int i=1;i<n;i++)e[i]=mo(e[i-1]*g,pp);
  51.      for(int m=2,t=n>>1;m<=n;m<<=1,t>>=1)
  52.        for(int i=0;i<n;i+=m)
  53.          for(int j=i;j<i+(m>>1);j++){
  54.            ll u=a[j],v=mo(a[j+(m>>1)]*e[(j-i)*t],pp);
  55.            a[j]=u+v;
  56.            if(a[j]>=pp)a[j]-=pp;
  57.            a[j+(m>>1)]=u-v;
  58.            if(a[j+(m>>1)]<0)a[j+(m>>1)]+=pp;
  59.          }
  60. }
  61. void Add(ll &a,ll b){
  62.     a+=b;
  63.     if(a>=pp)a-=pp;
  64. }
  65. int get(){
  66.     return (rand()<<10)+rand();
  67. }
  68. int main(){
  69.     freopen("count.in","r",stdin);
  70.     freopen("count.out","w",stdout);
  71.     n=read();
  72.     b[0]=inv[0]=1;
  73.     rep(i,1,n)b[i]=b[i-1]*i%pp,inv[i]=powmod(b[i],pp-2,pp);
  75.     f[1]=f2[1]=1;
  76.     rep(i,1,n)b1[i]=powmod(2,C(i,2),pp); 
  78.     rep(i,1,n)b2[i]=b1[i]*inv[i]%pp;
  79.     int nn=256,n2=nn*2;
  80.     rep(i,1,n)bel[i]=i/nn;
  81.     int num=0;
  82.     ll t=powmod(nn*2,pp-2,pp);
  83.         rep(i,1,n){
  84.         if(i%nn==0){
  85.             rep(j,0,nn*2)tt[j]=0;
  86.             rep(j,1,bel[i]-1){
  87.                 int t1=j*n2,t2=(bel[i]-j)*n2;
  88.                 rep(k,0,nn*2-1)
  89.                     tt[k]=(tt[k]+recf[t1+k]*recb[t2+k])%pp;
  90.             }
  91.             fnt(tt,nn*2,-1);
  92.             rep(j,0,nn*2-1)Sum[bel[i]*nn+j]=(Sum[bel[i]*nn+j]+tt[j]*t)%pp;
  93.         }
  94.         f[i]=mo(b1[i]-Sum[i]*b[i-1],pp);
  95.         f2[i]=f[i]*inv[i-1]%pp;
  97.         for(int j=1;j<i && j<nn;j++)
  98.             Sum[i+j]=(Sum[i+j]+f2[j]*b2[i]+f2[i]*b2[j])%pp;
  99.         if(i<nn)Add(Sum[i+i],f2[i]*b2[i]%pp);
  101.         if(i%nn==nn-1){
  102.             rep(j,0,nn*2)tt[j]=0;
  103.             rep(j,bel[i]*nn,i)tt[j%nn]=f2[j];
  104.             fnt(tt,nn*2,1);
  105.             rep(j,0,nn*2-1)recf[bel[i]*n2+j]=tt[j];
  107.             rep(j,0,nn*2)tt[j]=0;
  108.             rep(j,bel[i]*nn,i)tt[j%nn]=b2[j];
  109.             fnt(tt,nn*2,1);
  110.             rep(j,0,nn*2-1)recb[bel[i]*n2+j]=tt[j];
  111.         }
  112.     }
  113.     cout<<f[n]<<endl;
  114.     return 0;
  115. }

T3

表示以为根的子树里面，答案最大可能是多少（只考虑子树中的路径覆盖子树的情况）
那么有
如果一个树根被覆盖了，就用其他未被覆盖的值加上被覆盖的边的边权。
因为树是随机的，所以深度不会太深。表示节点所有的儿子的值的和减去它本身的值。相当于只要考虑覆盖了根节点的路径的值之和和路径长就可以了
总复杂度就可以是

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<cstdlib>
  7. using namespace std;
  8. typedef long long ll;
  9. typedef long double ld;
  10. typedef pair<int,int> pr;
  11. const double pi=acos(-1);
  12. #define rep(i,a,n) for(int i=a;i<=n;i++)
  13. #define per(i,n,a) for(int i=n;i>=a;i--)
  14. #define Rep(i,u) for(int i=head[u];i;i=Next[i])
  15. #define clr(a) memset(a,0,sizeof a)
  16. #define pb push_back
  17. #define mp make_pair
  18. ld eps=1e-9;
  19. ll pp=1000000007;
  20. ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
  21. ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
  22. ll read(){
  23.     ll ans=0;
  24.     char last=' ',ch=getchar();
  25.     while(ch<'0' || ch>'9')last=ch,ch=getchar();
  26.     while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
  27.     if(last=='-')ans=-ans;
  28.     return ans;
  29. }
  30. //head
  31. #define N 210000
  32. int head[N],v[N],Next[N],dep[N],fa[N][18],a[N],st[N],ed[N];
  33. int n,num,m,num2,num3,nn,head2[N],v2[N],Next2[N];
  34. int lson[N],rson[N],root=0;
  35. ll Sum,f[N],s[N][2],sa[N];
  36. struct node{
  37.     int x,y,z;
  38. }q[N];
  39. void add(int x,int y){
  40.     v[++num]=y;Next[num]=head[x];head[x]=num;
  41. }
  42. void add2(int x,int y){
  43.     v2[++num2]=y;Next2[num2]=head2[x];head2[x]=num2;
  44. }
  45. int Q[N],siz[N]; 
  46. void dfs(int u){
  47.     int t=0,w=1;Q[1]=u;
  48.     while(t<w){
  49.         u=Q[++t];
  50.         sa[u]=sa[fa[u][0]]+a[u];
  51.         for(int i=1;(1<<i)<=dep[u];i++)
  52.             fa[u][i]=fa[fa[u][i-1]][i-1];
  53.         for(int i=head[u];i;i=Next[i])
  54.             if(v[i]!=fa[u][0]){
  55.                 fa[v[i]][0]=u;
  56.                 dep[v[i]]=dep[u]+1;
  57.                 Q[++w]=v[i];
  58.             }
  59.         siz[u]=1;
  60.     }
  61.     per(i,w,2)siz[fa[Q[i]][0]]+=siz[Q[i]];
  62.     st[1]=1;
  63.     rep(i,1,n){
  64.         u=Q[i];
  65.         int t=st[u];ed[u]=st[u]+siz[u]-1;
  66.         for(int i=head[u];i;i=Next[i])
  67.             if(v[i]!=fa[u][0])st[v[i]]=t+1,t+=siz[v[i]];
  68.     }
  69. }
  70. int lca(int x,int y){
  71.     if(dep[x]<dep[y])swap(x,y);
  72.     per(i,17,0)
  73.         if(dep[x]-(1<<i)>=dep[y])x=fa[x][i];
  74.     if(x==y)return x;
  75.     per(i,17,0)
  76.         if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
  77.     return fa[x][0];
  78. }
  79. int lca2(int x,int y){
  80.     per(i,17,0)
  81.     if(dep[x]-(1<<i)>dep[y])x=fa[x][i];
  82.     return x;
  83. }
  84. void change(int &u,int l,int r,int x,int y,ll w,int k){
  85.     if(x>r || y<l)return ;
  86.     if(!u)u=++num3;
  87.     if(x<=l && y>=r){
  88.         s[u][k]+=w;
  89.         return;
  90.     }
  91.     int mid=(l+r)>>1;
  92.     change(lson[u],l,mid,x,y,w,k);
  93.     change(rson[u],mid+1,r,x,y,w,k);
  94. }
  95. ll find(int u,int l,int r,int x,int k){
  96.     if(!x)return 0;
  97.     if(!u)return 0;
  98.     if(l==r)return s[u][k];
  99.     int mid=(l+r)>>1;
  100.     if(x<=mid)return find(lson[u],l,mid,x,k)+s[u][k];
  101.     else return find(rson[u],mid+1,r,x,k)+s[u][k];
  102. }
  103. ll work2(int x,int y){
  104.     return find(root,1,n,st[x],1)-find(root,1,n,st[fa[y][0]],1)-(find(root,1,n,st[x],0)-find(root,1,n,st[y],0));
  105. }
  106. ll work(int x,int y,int z){
  107.     if(dep[x]<dep[y])swap(x,y);
  108.     if(y==z)return work2(x,y)+sa[x]-sa[fa[y][0]];
  109.     int t=lca2(y,z);
  110.     return work2(x,z)+work2(y,t)-f[t]+sa[x]+sa[y]-sa[z]-sa[fa[z][0]];
  111. }
  112. void dfs2(int u){
  113.     per(i,n,1){
  114.     u=Q[i];
  115.     f[u]=0;
  116.     for(int i=head[u];i;i=Next[i])
  117.         if(v[i]!=fa[u][0])f[u]+=f[v[i]];
  118.     for(int i=head2[u];i;i=Next2[i]){
  119.         int t=v2[i];
  120.         int x=q[t].x,y=q[t].y,z=q[t].z;
  121.         f[u]=max(f[u],work(x,y,z));
  122.     }
  123.     change(root,1,n,st[u],ed[u],f[u],0);
  124.     change(root,1,n,st[fa[u][0]],ed[fa[u][0]],f[u],1);
  125.     }
  126. }
  127. int main(){
  128.     freopen("max.in","r",stdin);
  129.     freopen("max.out","w",stdout);
  130.     n=read();
  131.     rep(i,1,n)a[i]=read();
  132.     rep(i,2,n){
  133.         int x=read(),y=read();
  134.         add(x,y);add(y,x);
  135.     }
  136.     dfs(1);
  137.     m=read();
  138.     rep(i,1,m)q[i].x=read(),q[i].y=read(),q[i].z=lca(q[i].x,q[i].y),add2(q[i].z,i);
  139.     dfs2(1);
  140.     cout<<f[1]<<endl;
  141.     return 0;
  142. }

T4

meet in the middle 左右两边各有种可能。从左右两边各挑选一个,使得其和小于且最大。
对所有左边所有的情况建01-trie树，对于右边的找其与左边所有的组合，最优的是多少。
若的最高位是，的最高位与trie树的某子树的为，那这个子树所有组合都是小于的，预处理出所有子树中的最大和，更新答案。

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<cstdlib>
  7. #include<set>
  8. using namespace std;
  9. typedef long long ll;
  10. typedef long double ld;
  11. typedef pair<int,int> pr;
  12. const double pi=acos(-1);
  13. #define rep(i,a,n) for(int i=a;i<=n;++i)
  14. #define per(i,n,a) for(int i=n;i>=a;--i)
  15. #define Rep(i,u) for(int i=head[u];i;i=Next[i])
  16. #define clr(a) memset(a,0,sizeof a)
  17. #define pb push_back
  18. #define mp make_pair
  19. #define fi first
  20. #define sc second
  21. ld eps=1e-9;
  22. ll pp=1000000007;
  23. ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
  24. ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
  25. ll read(){
  26.     ll ans=0;
  27.     char last=' ',ch=getchar();
  28.     while(ch<'0' || ch>'9')last=ch,ch=getchar();
  29.     while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
  30.     if(last=='-')ans=-ans;
  31.     return ans;
  32. }
  33. //head
  34. int nn=1,ans=0,n,m,tot=0;
  35. int son[2000000][2],Max[2000000];
  36. int a[50],b[50];
  37. void insert(int x,int s){
  38.     int t=1;
  39.     per(i,29,0){
  40.         int kk=(x>>i)&1;
  41.         if(!son[t][kk])son[t][kk]=++nn;
  42.         t=son[t][kk];
  43.         Max[t]=max(Max[t],s);
  44.     }
  45. }
  46. void query(int u,int dep,int x,int s){
  47.     if(!u)return;
  48.     if(dep==-1)return;
  49.     int kk=((x>>dep)&1)^((m>>dep)&1);
  50.     if(((m>>dep)&1)==1)ans=max(ans,s+Max[son[u][kk^1]]);
  51.     query(son[u][kk],dep-1,x,s);
  52. }
  53. void dfs1(int t1,int t2,int x,int s){
  54.     if(t1>t2){
  55.         tot+=1;
  56.         insert(x,s);
  57.         return;
  58.     }
  59.     dfs1(t1+1,t2,x,s);
  60.     dfs1(t1+1,t2,x^a[t1],s+b[t1]);
  61. }
  62. void dfs2(int t1,int t2,int x,int s){
  63.     if(t1>t2){
  64.         query(1,29,x,s);
  65.         return;
  66.     }
  67.     dfs2(t1+1,t2,x,s);
  68.     dfs2(t1+1,t2,x^a[t1],s+b[t1]);
  69. }
  70. int main(){
  71.     freopen("xor.in","r",stdin);
  72.     freopen("xor.out","w",stdout);
  73.     n=read();m=read();m+=1;
  74.     int ss=0;
  75.     rep(i,1,n)a[i]=read(),b[i]=read(),ss+=b[i];
  76.     dfs1(1,n/2,0,0);
  77.     dfs2(n/2+1,n,0,0);
  78.     cout<<ans<<endl;
  79.     return 0;
  80. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注