背景描述： 黑夜给了我黑色的眼睛 我却用它寻找光明 ——《一代人》 顾城 已知一个N个元素的非负整数序列A， 定义Bi = (Ai and A1) + (Ai and A2) + (Ai and A3)+ …… + (Ai and An) 定义Ci = (Ai or A1) + (Ai or A2) + … + (Ai or An) 给出B和C序列， 构造一个满足条件的A序列， 如果没有， 输出-1 输入格式： 第一行一个整数N。 接下来一行N个整数表示B序列 接下来一行N个整数表示C序列 输出格式： 如果有解， 输出一行N个整数表示你构造的A序列， SPJ很脆弱， 所以你构造的序列每个整数必须在[0,8191]这个区间内， 我们保证如果有解， 那么一定存在一个解满足每个元素均在[0,8191]内 否则输出-1 样例输入： 4 6 8 4 4 16 22 10 10 样例输出： 3 5 1 1 数据规模： 对于30%的数据， N = 2 对于70%的数据， N <= 200 对于100%的数据， N <= 100000， Bi , Ci<= 1000000000
我们想到容斥原理，A+B=A∩B+A∪B。 推论出A+B=A|B+A&B。 于是这题又变成了水题。复杂度才O(n)。
附程序：
//a+b = (a&b) + (a|b) #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<vector> #include<queue> #include<stack> #include<map> #include<set> #include<string> #include<iomanip> #include<ctime> #include<climits> #include<cctype> #include<algorithm> #define clr(a,x) memset(x,a,sizeof(x)) #define ll long long #ifdef WIN32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; const int maxn = 1e5+10; ll n,ans,b[maxn],c[maxn],aannss[maxn]; template <class T> inline void read(T &xx) { xx = 0; T flag = 1; char ch = (char)getchar(); while(ch<'0' || ch>'9') { if(ch == '-') flag = -1; ch = (char)getchar(); } while(ch>='0' && ch<='9') { xx = (xx<<1) + (xx<<3) + ch - '0'; ch = (char)getchar(); } xx *= flag; } int main() { freopen("problem.in","r",stdin); freopen("problem.out","w",stdout); read(n); for(int i = 1; i <= n; i++) read(b[i]); for(int i = 1; i <= n; i++) read(c[i]); for(int i = 1; i <= n; i++) ans += b[i] + c[i]; ans /= 2*n; for(int i = 1; i <= n; i++) { aannss[i] = ((b[i]+c[i])-ans)/n; if(aannss[i] > 8191 || aannss[i] < 0) { printf("-1"); return 0; } if(((b[i]+c[i])-ans)%n != 0) { printf("-1"); return 0; } } for(int i = 1; i <= n; i++) printf(AUTO" ",aannss[i]); return 0; }