模拟赛 c7-A xor-尧图网络科技

题目描述

蜗蜗有个密码盒，每个密码盒上原本写着⼀个⾮负整数。第个密码盒上的数字是。另有张标签，每张标签上也写着⼀个⾮负整数，标签上的数字分别是。蜗蜗可以任意重新排列这些标签，然后把它们⼀⼀贴到密码盒上。蜗蜗想找⼀个⾮负整数，使得可以通过某种贴标签⽅式，让每个密码盒都满⾜：

\(a_i\) \(xor\) \(b_i = x\)

这⾥\(xor\)表示按位异或。注意，重新排列标签后，式⼦中的表示贴到第个密码盒上的标签数字。请你找出所有可能的，并按从⼩到⼤的顺序输出。

输入格式

第⼀⾏输⼊⼀个整数\(N\) 。

第⼆⾏输⼊\(N\)个整数 \(a_i\)。

第三⾏输⼊\(N\)个整数 \(b_i\)。

输出格式

第⼀⾏输出⼀个整数\(K\)，表示合法的\(x\)的个数。

接下来\(K\)⾏，每⾏输出⼀个合法的\(x\)。

合法的\(x\)必须按从⼩到⼤的顺序输出。

样例输⼊1

0 1

样例输出1

样例输⼊2

0 1 2

0 1 4

样例输出2

样例解释

对于样例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;
}