傳送門
題目：給定兩個整數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 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <cstdio> 5 #include <stack> 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 <<" before" << endl; 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<ll > 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 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/145741.html
標籤：其他