[题解][洛谷P1633] 二进制

题目描述
有三个整数A,B,C,构造三个整数X,Y,Z满足：
1.A,B,C在二进制下1的数量分别与X,Y,Z相等；
2.X,Y,Z在二进制下的长度不超过A,B,C的最大长度；
3.X+Y=Z。
输出Z的最小值，若不存在Z，输出-1。

题意分析
首先考虑X,Y在什么情况下会使1的数量发生改变。
设x,y,z分别表示X,Y,Z中1的数量，则有：
1）x+y<z时，不论怎么凑1都不能使1的数量增多，则无解；
2）x+y=z时，只要每一位都是1和0相加即可得到Z；
3）x+y>z时，此时1的数量更多，需要考虑通过进位消除1。
对于一段连续的1111，加上1变成10000。可以得到若干连续的1可以通过+1减少1的数量。
考虑如何得到最小的Z，若有多个连续进位，可以合并成一个连续进位，因此只需考虑一个连续进位。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int a[4]={0,0,0,0};
		int cnt[4]={0,0,0,0};
		int len[4]={0,0,0,0};
		cin>>a[1]>>a[2]>>a[3];
		for(int i=1;i<=3;i++){
			while(a[i]){
			if(a[i]%2)cnt[i]++;
			a[i]/=2;
			len[i]++;
			}
		}
		int l=max(len[1],max(len[2],len[3]));
		int L=max({cnt[1]+cnt[2]-cnt[3]+1+max(2*cnt[3]-cnt[2]-cnt[1],0),cnt[1]+1,cnt[2]+1});
		if(cnt[1]+cnt[2]-cnt[3]==0)cout<<(1<<cnt[3])-1<<"\n";
		else if(cnt[1]+cnt[2]-cnt[3]<0||!len[3])cout<<-1<<"\n";
		else if(L>l)cout<<-1<<"\n";
		else{
			int d=cnt[1]+cnt[2]-cnt[3];
			int ans=(1<<(L-1))+(1<<(L-d-1))-1;
			for(int i=L;i<cnt[1]+cnt[2];i++)ans|=1<<(i-d);
			cout<<ans<<"\n";
		}
	}
} 

DLC
是否有别的方法解决呢？
上述方法解决问题的规模是O(logn),由于X,Y,Z均处于2³⁰的规模，因此只能在O(logn⁵）的规模下解决。
考虑数位dp，以dp[s][i][j][k][0/1]表示执行到最低s位，A,B,C分别用了i,j,k个1，最高位产生/不产生进位下Z的最小值。
以此思路，只需枚举X,Y用1还是用0，就可以得到状态转移和Z的变化情况。