题目描述
蜗蜗有 个密码盒，每个密码盒上原本写着⼀个⾮负整数。第 个密码盒上的数字是 。 另有 张标签，每张标签上也写着⼀个⾮负整数，标签上的数字分别是 。蜗蜗可以任意重新排列这些标签，然 后把它们⼀⼀贴到密码盒上。 蜗蜗想找⼀个⾮负整数 ，使得可以通过某种贴标签⽅式，让每个密码盒都满⾜：
\(a_i\) \(xor\) \(b_i = x\)
这⾥\(xor\)表示按位异或。注意，重新排列标签后，式⼦中的 表示贴到第 个密码盒上的标签数字。 请你找出所有可能的 ，并按从⼩到⼤的顺序输出。
输入格式
第⼀⾏输⼊⼀个整数\(N\) 。
第⼆⾏输⼊\(N\)个整数 \(a_i\)。
第三⾏输⼊\(N\)个整数 \(b_i\)。
输出格式
第⼀⾏输出⼀个整数\(K\)，表示合法的\(x\)的个数。
接下来\(K\)⾏，每⾏输出⼀个合法的\(x\)。
合法的\(x\)必须按从⼩到⼤的顺序输出。
样例输⼊1
2
0 1
0 1
样例输出1
2
0
1
样例输⼊2
3
0 1 2
0 1 4
样例输出2
0
样例解释
对于样例1：
当\(x=0\)时，可以保持标签顺序不变，此时 ，\(0\) \(xor\) \(0 = 0\)，\(1\) \(xor\) \(1 = 0\) 。
当\(x=1\)时，可以交换两张标签，此时 ，\(0\) \(xor\) \(1 = 1\)，\(1\) \(xor\) \(0 = 1\) 。 所以⼀共有\(2\)个合法的\(x\)，分别是\(0\)和\(1\)。
对于样例2： ⽆论怎样重新排列标签，都⽆法让所有密码盒异或标签后的结果相同，所以合法的\(x\)个数为\(0\)。
数据范围
对于100%的数据，保证 \(1≤N≤2000\) , \(0≤A_i,B_i<2^{30}。\)
算法分析
首先暴力可以得出：用双重循环枚举每一个可能的\(x\)，依次check，时间复杂度\(O(n^3logn)\)，会TLE。所以考虑优化，不难想到，因为所有可能的\(x\)，都在\(A_1\) \(xor\) \(B_1,B_2,...,B_n\)中，所以只要枚举前面那个式子就可以了，时间复杂度优化成了\(O(n^2logn)\)，可以通过此题。
AC代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
int mx = 0;
ll a[2005];
ll b[2005];
set<ll> st;
vector<int> c;
vector<int> d;
bool check(ll x){c.clear();//清空数组for(int i = 1; i<=n; i++){ll t = x^b[i];//算异或值c.push_back(t);}sort(c.begin(),c.end());//排序后才能比较if(c==d){//判等return true;}else{return false;}
}
int main(){//freopen("xor.in","r",stdin);//freopen("xor.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i = 1; i<=n; i++){cin>>a[i];}for(int i = 1; i<=n; i++){cin>>b[i];}sort(a+1,a+1+n);//排序for(int i = 1; i<=n; i++){d.push_back(a[i]);//放入vector}for(int i = 1; i<=n; i++){ll t = a[1]^b[i];//枚举每一个可能的xif(check(t)){//判断st.insert(t);//如果可以，放入set}}cout<<st.size()<<'\n';//输出个数for(auto i = st.begin(); i!=st.end(); i++){cout<<*i<<'\n';//从小到大输出}return 0;
}
总结
思路不难想，代码也不难写，可以评个橙题。