給定一個集合A，一個集合B，A，B元素個數相等，然后問是否存在一個數X使得A中的元素均與這個數進行按位異或操作后的結果為B集合，如果存在輸出最小的數，不存在輸出-1。

思路：由于給定的N為奇數，所以能夠根據二進制位的最右邊位確定唯一的分組，然后只需要判定這個分組是否合理即可。

分組是這樣劃分的，如有A、B兩組數據，把A組根據末位0和1分成兩組，B組同理劃分，那么只有00配對或者是01配對，這有各組中數的個數確定。配對模式確定后，再通過30次判定即可。

#include <cstdlib> #include <cstdio> #include <iostream> #include <cstring> #include <cstdio> #include <cstdlib> using namespace std;const int MaxN = 100005; int a[MaxN], b[MaxN], N; int ans[40]; int st[4][MaxN]; int cnt[4], bit[4][40]; // N是奇數就好做了int cal(int x, int b[]) {for (int i = 0; i < 30; ++i) {if ((x >> i) & 1) ++b[i];} }int judge(int i, int mode) {// 如果是模式0，即st0 與 st2 匹配 if (mode == 0) {if (bit[0][i] == bit[2][i] && bit[1][i] == bit[3][i]) return 0;else if (bit[0][i] == cnt[2]-bit[2][i] && bit[1][i] == cnt[3]-bit[3][i]) return 1;else return -1;} else { // 如果是模式1，即st0 與 st3匹配 if (bit[0][i] == bit[3][i] && bit[1][i] == bit[2][i]) return 0;else if (bit[0][i] == cnt[3]-bit[3][i] && bit[1][i] == cnt[2]-bit[2][i]) return 1;else return -1;} }void gao() {for (int i = 0; i < 4; ++i) {memset(st[i], 0, sizeof (st[i]));memset(bit[i], 0, sizeof (bit[i]));}memset(ans, 0, sizeof (ans));memset(cnt, 0, sizeof (cnt));for (int i = 0; i < N; ++i) {if (!(a[i] & 1)) st[0][cnt[0]++] = i;else st[1][cnt[1]++] = i;if (!(b[i] & 1)) st[2][cnt[2]++] = i;else st[3][cnt[3]++] = i;}for (int i = 0; i < 4; ++i) {for (int j = 0; j < cnt[i]; ++j) {if (i < 2) cal(a[st[i][j]], bit[i]);else cal(b[st[i][j]], bit[i]);}}int mode = -1;// 由最低位的1的個數劃分模式，由于N為奇數，所以劃分的方式是唯一的 if (cnt[0] == cnt[2]) ans[0] = mode = 0;else if (cnt[0] == cnt[3]) ans[0] = mode = 1;if (mode == -1) {puts("-1");return;}for (int i = 1; i < 30; ++i) {ans[i] = judge(i, mode);if (ans[i] == -1) {puts("-1");return;}}int ret = 0;for (int i = 0; i < 30; ++i) {ret += ans[i] ? (1 << i) : 0;}printf("%d\n", ret); }int main() {while (scanf("%d", &N) == 1) {for (int i = 0; i < N; ++i) {scanf("%d", &a[i]);}for (int i = 0; i < N; ++i) {scanf("%d", &b[i]);}gao();}return 0; }

?

總結

以上是生活随笔為你收集整理的Acdream Xor 简单数学的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。