[NOIP模拟题][位运算][建模][并查集]

T1

第一题：信(believe.cpp/c/pas) 背景描述： 一切死亡都有冗长的回声 —— 《一切》北岛 给定一个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[1]-A[n]都用到，所有我们应该从这里下手 预处理出A[1]-A[n]所有数二进制第j为1的总和，记为sum[j] 那么对于B[i]的第j为，若A[i]第j位为0，则无贡献否则这一位贡献为sum[j]*(1<

#include<cstring> #include<cstdio> #include<cctype> #include<algorithm> #ifdef WIN32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; typedef long long LL; const int maxn=1e5+5; const int maxd=18; int n,A[maxn],sum[maxd]; LL B[maxn],C[maxn]; int readint() { int x=0; char ch=getchar(); while (!isdigit(ch)) ch=getchar(); while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x; } int main() { freopen("beleive.in","r",stdin); freopen("believe.out","w",stdout); n=readint(); for (int i=1;i<=n;i++) { A[i]=readint(); for (int j=0;j<maxd;j++) if (A[i]&(1<<j)) sum[j]++; } for (int i=1;i<=n;i++) for (int j=0;j<maxd;j++) if (A[i]&(1<<j)) { B[i]+=(LL)sum[j]*(1<<j); C[i]+=(LL)n*(1<<j); } else C[i]+=(LL)sum[j]*(1<<j); for (int i=1;i<=n;i++) printf(AUTO" ",B[i]); putchar('\n'); for (int i=1;i<=n;i++) printf(AUTO" ",C[i]); }

T2

第二题：心（heart.cpp/c/pas) 背景描述： 不是一切深渊都是灭亡 不是一切灭亡都覆盖在弱者的头上 ——《这也是一切》 舒婷 有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

考试的时候这道题真的是完完全全打偏了，我果然还是太久没有碰过图了 把每一种颜色看成一个点，一个盒子看成连接这两个点的边，显然的，若要满足条件，整个图中不能存在环，要消去一个环，去掉上面任意一条边都是等效的，那么用并查集实现就可以了

#include<cstring> #include<cstdio> #include<cctype> #include<algorithm> #ifdef WIN32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; typedef long long LL; const int maxn=1e5+5; int n,m,ans,fa[maxn<<1]; int readint() { int x=0; char ch=getchar(); while (!isdigit(ch)) ch=getchar(); while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x; } int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } int main() { freopen("heart.in","r",stdin); freopen("haert.out","w",stdout); ans=n=readint(); m=readint(); for (int i=1;i<=m;i++) fa[i]=i; for (int i=1;i<=n;i++) { int u=readint(),v=readint(); u=find(u); v=find(v); if (u^v) fa[v]=u; else ans--; } printf("%d",ans); return 0; }

T3

第三题：题(problem.cpp/c/pas) 背景描述： 黑夜给了我黑色的眼睛 我却用它寻找光明 ——《一代人》 顾城 已知一个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

神TM考试时把8191看成819了，导致暴力分都没有 本题核心解题思路 A&B+A|B=A+B 然后就可以秒掉了

#include<cstring> #include<cstdio> #include<cctype> #include<algorithm> #ifdef WIN32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; typedef long long LL; const int maxn=1e5+5; const int maxd=18; int n,A[maxn],sum[maxd]; LL B[maxn],C[maxn]; int readint() { int x=0; char ch=getchar(); while (!isdigit(ch)) ch=getchar(); while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x; } int main() { freopen("beleive.in","r",stdin); freopen("believe.out","w",stdout); n=readint(); for (int i=1;i<=n;i++) { A[i]=readint(); for (int j=0;j<maxd;j++) if (A[i]&(1<<j)) sum[j]++; } for (int i=1;i<=n;i++) for (int j=0;j<maxd;j++) if (A[i]&(1<<j)) { B[i]+=(LL)sum[j]*(1<<j); C[i]+=(LL)n*(1<<j); } else C[i]+=(LL)sum[j]*(1<<j); for (int i=1;i<=n;i++) printf(AUTO" ",B[i]); putchar('\n'); for (int i=1;i<=n;i++) printf(AUTO" ",C[i]); }