我去考fop_zz的； 结果他真的秒掉了； https://www.luogu.org/problem/show?pid=1633 我们考虑三个长度为l的串； 显然如果这3个串符合条件的话； 我们就只要保证增加2^l级别的值满足加法原则就好了； 所以我们大力dp; f[i][a][b][c][0/1] i表示位数 a表示x串前i-1个字符所有的1的数量； b，c同理； 0/1表示c串在第i位是1还是0； 预处理 f[1][0][0][0][0]=0;其他都是inf； 转移就是考虑当前第i位a,b要不要放1； 然后对应的计算c新增的值；
#include<bits/stdc++.h> #define Ll long long using namespace std; const int N=35; Ll f[N][N][N][N][2],v; int w,A,B,C,n; int er(int x){ int ans=0,sum=0; for(;x;x/=2,sum++)if(x&1)ans++; n=max(n,sum); return ans; } int main() { scanf("%d",&w); while(w--){ scanf("%d%d%d",&A,&B,&C); n=0;memset(f,14,sizeof f); A=er(A);B=er(B);C=er(C); f[1][0][0][0][0]=0; for(int i=1;i<=n;i++) for(int a=0;a<=A;a++) for(int b=0;b<=B;b++) for(int c=0;c<=C;c++){ v=f[i][a][b][c][0]; f[i+1][a ][b ][c ][0]=min(f[i+1][a ][b ][c ][0],v); f[i+1][a+1][b+1][c ][1]=min(f[i+1][a+1][b+1][c ][1],v+(1<<i)); f[i+1][a+1][b ][c+1][0]=min(f[i+1][a+1][b ][c+1][0],v+(1<<i-1)); f[i+1][a ][b+1][c+1][0]=min(f[i+1][a ][b+1][c+1][0],v+(1<<i-1)); v=f[i][a][b][c][1]; f[i+1][a ][b ][c+1][0]=min(f[i+1][a ][b ][c+1][0],v); f[i+1][a+1][b+1][c+1][1]=min(f[i+1][a+1][b+1][c+1][1],v+(1<<i)); f[i+1][a+1][b ][c ][1]=min(f[i+1][a+1][b ][c ][1],v+(1<<i-1)); f[i+1][a ][b+1][c ][1]=min(f[i+1][a ][b+1][c ][1],v+(1<<i-1)); } if(f[n+1][A][B][C][0]>(1<<30))printf("-1\n");else printf("%lld\n",f[n+1][A][B][C][0]); } }