题目：给定两个整数u和v，找到最短的数组，使其满足：该数组的（xor）和为u，累加和为v。
思路：我们组成的数组累加和为v，我们可以用二进制表示v，我们知道（xor）会导致相同位为0。我们可以利用前面的内容，拆分v每一位上的信息，例如”100″，我们可以拆成两个”010″，我们可以用一个数组bit表示当前位有几个，而我们最后需要的答案为u，也把它转为二进制x。对于bit数组，我们就可以利用每一位的个数，如果这一位上个数为偶数，则（xor）和后该位一定是0，如果是奇数，则（xor）和后该为一定是1，这样我们通过拆分高位来凑低位或者使得满足条件。最后我们凑出的bit数组一定是除了x中二进制位1的bit[x]是奇数，其他都是偶数，这样（xor）和就是u，累加和也一定是u，因为我们只是差分了高位。
注意点：
①u > v 答案一定是 “-1”
②u = 0 时 如果v为偶数，则输出两个v/2，如果是奇数就是”-1″
③其他一般情况就是去凑
1 #include2 #include <string> 3 #include 4 #include 5 #include 6 7 #define ll long long 8 #define pb push_back 9 10 using namespace std; 11 12 int bit[100]; 13 int x[100]; 14 15 void solve() 16 { 17 ll sum, bxor; 18 cin >> bxor >> sum; 19 20 if(bxor > sum){ 21 cout << "-1" << endl; 22 }else if(bxor == 0 && sum % 2 == 0 && sum){ 23 cout << "2" << endl << sum / 2 << " " << sum / 2 << endl; 24 }else if(bxor == 0 && sum % 2 == 1){ 25 cout << "-1" << endl; 26 }else{ 27 28 //取出二进制的信息 29 for(ll i = 0; i < 64; ++i){ 30 bit[i] = (ll)(sum >> i) & 1; 31 } 32 33 for(ll i = 0; i < 64; ++i){ 34 x[i] = (ll)(bxor >> i) & 1; 35 } 36 // cout < 37 // for(int i = 0; i < 64; ++i) cout << bit[i] << " "; 38 // cout << endl; 39 // for(int i = 0; i < 64; ++i) cout << x[i] << " "; 40 // cout << endl; 41 42 //先让x存在的1位，bit都存在 43 for(int i = 0; i < 64; ++i){ 44 if(!x[i] || (x[i] && bit[i])) continue; 45 46 for(int j = i + 1; j < 64; ++j){ 47 if(!bit[j]) continue; 48 for(int k = j; k > i; --k){ 49 bit[k] -= 1; 50 bit[k - 1] += 2; 51 } 52 break; 53 } 54 } 55 // cout << "first change" << endl; 56 // for(int i = 0; i < 64; ++i) cout << bit[i] << " "; 57 // cout << endl; 58 // for(int i = 0; i < 64; ++i) cout << x[i] << " "; 59 // cout << endl; 60 for(int i = 64; i > 0; --i){ 61 if(!bit[i]) continue; 62 //bit为奇数，但是x为0，说明该为需要拆成两个低位，这样就可以通过 63 //xor使得该1变成0 64 if(bit[i] % 2 == 1 && !x[i]){ 65 bit[i]--; 66 bit[i - 1] += 2; 67 } 68 //如果bit为偶数，x为1，则需要该位数量减去1，变成奇数 69 //xor能让该位变成1 70 else if(bit[i] % 2 == 0 && x[i]){ 71 bit[i]--; 72 bit[i - 1] += 2; 73 } 74 } 75 // cout << "second change" << endl; 76 // for(int i = 0; i < 64; ++i) cout << bit[i] << " "; 77 // cout << endl; 78 // for(int i = 0; i < 64; ++i) cout << x[i] << " "; 79 // cout << endl; 80 81 //判断拆出来的bit是不是符合题意 82 int even = 1; 83 for(int i = 0; i < 64; ++i){ 84 if(bit[i] % 2 == 0 && !x[i]) continue; 85 if(bit[i] % 2 && x[i]) continue; 86 even = 0; 87 break; 88 } 89 if(!even) cout << "-1" << endl; 90 else{ 91 vector ans; 92 // for(int i = 0; i < 10; ++i) cout << bit[i] << " "; 93 // cout << endl; 94 95 while(1){ 96 ll num = 0; 97 for(ll i = 0; i < 64; ++i){ 98 if(!bit[i]) continue; 99 num += ((ll)1 << i); 100 //cout << num << endl; 101 // cout << ((ll)1 << i) << endl; 102 bit[i]--; 103 } 104 if(num) ans.pb(num); 105 else break; 106 } 107 cout << ans.size() << endl; 108 if(ans.size()){ 109 for(auto x : ans) cout << x << " "; 110 cout << endl; 111 } 112 } 113 114 } 115 116 117 } 118 119 int main() 120 { 121 122 ios::sync_with_stdio(false); 123 cin.tie(0); 124 cout.tie(0); 125 solve(); 126 //cout << "ok" << endl; 127 return 0; 128 }
Original: https://www.cnblogs.com/SSummerZzz/p/13547455.html
Author: SummerMingQAQ
Title: CF 1325D Ehab the Xorcist
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584297/
转载文章受原作者版权保护。转载请注明原作者出处！