第一题：信

背景描述：

一切死亡都有冗长的回声 —— 《一切》北岛 给定一个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序列。

输入格式：

第一行一个整数N表示序列长度 接下来一行N个整数， 第i个整数为Ai

输出格式：

第一行N个整数输出B序列 第二行N个整数输出C序列

样例输入：

4 3 5 1 1

样例输出：

6 8 4 4 16 22 10 10

数据规模：

对于50%的数据， N <= 1000 对于100%的数据， N <= 100000， Ai <= 100000

注意事项：

输入量较大， 请使用比较快的例如scanf的读入方式， 最好不要采用cin。

简单题，将整个a串用二进制处理，第0位上的1有多少，第1位上的1有多少…对于b串，如果对应的a的某一位上有1，bi+=(1<<位数)×num[位数]；对于c串，如果对应的a的某一位上有1，ci+=(1<<位数)×n，否则ci+=(1<<位数)×num[位数]。 代码：

//一切死亡都有冗长的回声 //—— 《一切》北岛 #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #ifdef WIN32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; long long a[100005],b[100005],c[100005],tmp[20]; inline long long read() { long long x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void presolve(long long num) { for(int i=0;i<=18;i++) if(((num>>i)&1)==1) tmp[i]++; } int main() { freopen("beleive.in","r",stdin);//严格按照题意描述输入 freopen("believe.out","w",stdout); long long n=read(); for(long long i=1;i<=n;i++) { a[i]=read(); presolve(a[i]); } for(long long i=1;i<=n;i++) for(long long j=0;j<=18;j++) if(((a[i]>>j)&1)==1) b[i]+=(1<<j)*tmp[j]; for(long long i=1;i<=n;i++) { for(long long j=0;j<=18;j++) if(((a[i]>>j)&1)==1) c[i]+=(1<<j)*n; else c[i]+=(1<<j)*tmp[j]; } for(long long i=1;i<=n;i++) { printf(AUTO,b[i]); printf(" "); } printf("\n"); for(long long i=1;i<=n;i++) { printf(AUTO,c[i]); printf(" "); } return 0; }

第二题：心

背景描述：

不是一切深渊都是灭亡 不是一切灭亡都覆盖在弱者的头上 ——《这也是一切》 舒婷 有N个透明的盒子， 每个盒子里面有两个不同颜色的球， 总共有M种颜色。 Alice和Bob又在玩游戏， 具体的， Alice会从N个盒子里面选出若干个， Bob再从Alice选出的盒子里面选出一些（不能不选）， 如果在Bob选出的盒子中， 每个颜色的球都总共出现了偶数次（0次也是偶数次）， 那么Bob胜利， 否则Alice胜利 在Alice和Bob都足够聪明的情况下， Alice想知道自己在能够获胜的前提下， 第一次最多可以选出几个盒子

输入格式：

第一行有两个整数N和M， 意义如题 接下来N行， 第i+1行两个整数表示第i+1个盒子里面的两个球分别是什么颜色的

输出格式：

一行一个整数表示Alice最多可以选多少个盒子

样例输入：

3 3 1 2 2 3 2 3

样例输出：

2

数据规模：

对于30%的数据， N <= 10 对于50%的数据， N <= 20 对于100%的数据， N <= 100000， M <= 2N

考试时写了个并查集判重，AC，但有一点不解，下来想通了。 我的困惑是有没有可能出现选3个、5个等奇数的情况，但发现：就算Alice选了奇数个，Bob可以只选2个，所以我只需要每次输入时用并查集存储，如果遇到两种颜色已经在同一个并查集了，就ans–（ans初值为n）。 代码：

//不是一切深渊都是灭亡 //不是一切灭亡都覆盖在弱者的头上 //——《这也是一切》 舒婷 #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #ifdef WIN32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; int fa[200005]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline int find(int x) { if(x!=fa[x])return fa[x]=find(fa[x]); return fa[x]; } int main() { freopen("heart.in","r",stdin); freopen("haert.out","w",stdout);//严格按照题意输出 int n=read(),m=read(),ans=n; for(int i=1;i<=m;i++) fa[i]=i; for(int i=1;i<=n;i++) { int a=read(),b=read(); int f1=find(a),f2=find(b); if(f1!=f2)fa[f1]=f2; else ans--; } printf("%d",ans); return 0; }

第三题：题

背景描述：

黑夜给了我黑色的眼睛 我却用它寻找光明 ——《一代人》 顾城 已知一个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

考试时写了个40分的。 其实考试时都推得差不多了，就差临门一脚。 对于任意整数x、y，满足(x&y)+(x|y)=x+y，那么bi+ci=n*ai+sum（sum为a串之和）这个式子刷题的时候都遇到过。 那么直接将所有的b和c加起来除以2n即可。 需要注意的是：当tot不是2n的倍数，或者算出来的a值大于8191的话，输出-1。 代码：

//黑夜给了我黑色的眼睛 //我却用它寻找光明 //——《一代人》 顾城 #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #ifdef WIN32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; long long b[100005],c[100005],a[100005],s[100005],tot; inline long long read() { long long x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { freopen("problem.in","r",stdin); freopen("problem.out","w",stdout); long long n=read(); for(int i=1;i<=n;i++) b[i]=read(); for(int i=1;i<=n;i++) { c[i]=read();s[i]=c[i]+b[i]; tot+=s[i]; } if(tot%(2*n)!=0) { printf("-1"); return 0; } tot/=(2*n); for(int i=1;i<=n;i++) { a[i]=(s[i]-tot)/n; if(a[i]>8191) { printf("-1"); return 0; } } for(int i=1;i<=n;i++) { printf(AUTO,a[i]); printf(" "); } return 0; }

真不愧是信心题。 明天就是noip了，加油吧！