数位统计+hdu3972(dbl)

2019-04-14 21:08发布

站内文章 / 模拟电子
16468 0 1406
题意：给你3*N+2个数，找出其中两个特别的数
 Case 1：两个数相同 　　我们只要把所有数字的各个数位的二进制个数保存下来，模3即可 　　模剩下的数组里面非零部分必定是2，把二进制还原即可 Case 2：两个数不同 　　两个数必定有一个位上面的二进制表示不同 　　开一个[i][j]31*31的数组，意思是第i位是1的所有数字第j位为1的个数 　　对数组里面的所有元素模3 　　接着，有一个很显然的想法，两个数二进制不同，那么必定有一个[i][i]是1 　　把i处保存的数还原，得到一个解 　　然后还有一个数是不能用同样的方法来找的，因为可能a&b==a 　　也就是说，这种方法只能找到b，找不到a 　　找a其实只要把[i][i]为2的二进制个数全部减去b的二进制个数， 　　生下来的就是a的，还原即可 #include #include #include #include #include using namespace std; const int maxn=32; int dig[maxn]; int dp[maxn][maxn],n; int main() { freopen("in.txt","r",stdin); int t,x,i,j,k; scanf("%d",&t); while(t--) { scanf("%d",&n); memset(dig,0,sizeof(dig)); memset(dp,0,sizeof(dp)); for(i=0;i>1,sum>>1); } }