今天有人品爆发，240分，但是第三题没特判，第一题没用高精度也是可以GG的…… 明天就是NOIP了，高一党就全当体会一下吧！（P.S.今天有两个高一的来考试（不听劝啊~），于是乎……但愿没影响到他们考试的心情）

每日推荐!

没错，这次的每日推荐就是游戏王！！！ 从小学二年级开始，我看见了游戏王的起起伏伏，也经历了从萌新到菜鸟，再到现在的一般般的水平，用游戏王作为我今年noip的最后一份推荐，就是想贯彻游戏王决斗中除强大的计算外更吸引我的精神，never give up！！ 所以这次就以一句帅气的话来告诉世界，高一党有我在，而我也一定要创造奇迹！！！！（这flag立的………………） than ：： 所列哇多噶那！！！（千星大大快更新！！！！）

第一题：信(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。//使用读入优化readin（）；注：template< class T >

思考与题解

第一题： 考虑每一位对每个数的贡献， 令cnt[i]为二进制第i位为1的数的个数。 如果第j个数， 第i位为1， 那么第i位对Bj的贡献为cnt[i] * (1 << i), 对Cj的贡献 为n * (1 << i) 否则， 对Bj的贡献为０, 对Cj的贡献为cnt[i] * (1 << i) 复杂度N*logV, V代表值域 题解已经写得很清晰了……小编就不再赘述了。

code

呜呜呜~~没有标答快……

#include<set> #include<list> #include<deque> #include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cstdlib> #include<string> #include<vector> #include<ctime> #include<stack> #include<map> #define Li(x) x<<1 #define Ri(x) x<<1|1 #define clr(x) memset((x),0,sizeof(x)) #define cld(x) memset((x),127/2,sizeof(x)) #define smin(x,y) x=min(x,y) #define smax(x,y) x=max(x,y) #define smin(x,y) x=min(x,y) #define fmax(x,y,z) max(x,max(z,y)) #define fmin(x,y,z) min(x,min(z,y)) #define res(i,x,y) for(int i=x;i<=y;i++) #define rez(i,x,y) for(int i=x;i>=y;i--) #define resl(i,x,y) for(ll i=x;i<=y;i++) #define rezl(i,x,y) for(ll i=x;i>=y;i--) #define INF 2100000000 #define MOD 1000000007 #define ll long long #define N 200010 #define P 65536 #ifdef win32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; template <class T> inline void readin(T &resez){ static char ch; while((ch=getchar())<'0'||ch>'9'); resez=ch-48; while((ch=getchar())>='0'&&ch<='9') resez=resez*10+ch-48; } const ll M = 1e5+10; ll n,num[21],s[M],a,C[M],B[M],cnt[21]; ll power(ll a,ll b){ ll ans=1; while(b){ if(b%2==1){ ans=ans*a; } a=a*a; b/=2; } return ans; } int main(){ freopen("beleive.in","r",stdin); freopen("believe.out","w",stdout); readin(n); resl(i,1,n){ readin(a); resl(j,0,17){ if((1<<j)&a) num[j]++; else cnt[j]++; } s[i]=a; } resl(i,1,n){ resl(j,0,17){ if((1<<j)&s[i]){ B[i]+=power(2,j)*(num[j]); } } cout<<B[i]<<' '; } printf("\n"); resl(i,1,n){ resl(j,0,17){ if((1<<j)&s[i]) { C[i]+=power(2,j)*(num[j]+cnt[j]); } else{ C[i]+=power(2,j)*(num[j]); } } cout<<C[i]<<' '; } return 0; }

标答

这次标答的却比所有人都优……

//#include <bits/stdc++.h> #include <iostream> #include <cstdio> #ifdef WIN32 #define LLD "%I64d" #else #define LLD "%lld" #endif using namespace std ; int n ; const int MAXN = 100010 ; typedef long long LL ; int cnt[MAXN], a[MAXN] ; LL b[MAXN], c[MAXN]; int main() { freopen("beleive.in", "r", stdin) ; freopen("believe.out", "w", stdout) ; scanf("%d", &n) ; for (int i = 1; i <= n; i ++) scanf("%d", &a[i]) ; for (int i = 1; i <= n; i ++) { for (int j = 0; j < 20; j ++) { if ((a[i] >> j) & 1) cnt[j] ++ ; } } for (int i = 1; i <= n; i ++) { for (int j = 0; j < 20; j ++) { if ((a[i] >> j) & 1) { b[i] += 1LL * cnt[j] * (1 << j) ; c[i] += 1LL * n * (1 << j) ; } else { c[i] += 1LL * cnt[j] * (1 << j) ; } } } for (int i = 1; i <= n; i ++) { printf(LLD "%c", b[i], (i == n ? 10 : ' ')) ; } for (int i = 1; i <= n; i ++) { printf(LLD "%c", c[i], (i == n ? 10 : ' ')) ; } }

第二题：心（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

思考与题解

第二题： 将每一种颜色的球看成点， 那么一个盒子就是一条连接两个点的边。 选出的盒子如果构成了环， 那么Bob胜， 否则Alice胜 也就是说我们现在要选出尽量多的边， 使得不存在环， 直接并查集即可 并查集在此处

code

小编是通过建图来解决的………………很慢…………

#include<set> #include<list> #include<deque> #include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cstdlib> #include<string> #include<vector> #include<ctime> #include<stack> #include<map> #define Li(x) x<<1 #define Ri(x) x<<1|1 #define clr(x) memset((x),0,sizeof(x)) #define cld(x) memset((x),127/2,sizeof(x)) #define smin(x,y) x=min(x,y) #define smax(x,y) x=max(x,y) #define smin(x,y) x=min(x,y) #define fmax(x,y,z) max(x,max(z,y)) #define fmin(x,y,z) min(x,min(z,y)) #define res(i,x,y) for(int i=x;i<=y;i++) #define rez(i,x,y) for(int i=x;i>=y;i--) #define INF 2100000000 #define MOD 1000000007 #define ll long long #define N 200010 #define P 65536 #ifdef win32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; const int M = 2e5+5; int n,m,a,b,be[M],tot,num[M],ans; template <class T> inline void readin(T &resez){ static char ch; while((ch=getchar())<'0'||ch>'9'); resez=ch-48; while((ch=getchar())>='0'&&ch<='9') resez=resez*10+ch-48; } struct Edge{ int from,to; int belong; }edge[M]; vector<int> g[M]; void dfs(int s){ for (int i=0;i<g[s].size();i++){ int v=g[s][i]; if(!be[v]){ be[v]=be[s]; dfs(v); } } } int main(){ freopen("heart.in","r",stdin); freopen("haert.out","w",stdout); cin>>n>>m; res(i,1,n){ readin(a);readin(b); g[a].push_back(b);g[b].push_back(a); edge[i].to=a;edge[i].from=b; } res(i,1,m){ if(!be[i])be[i]=++tot; dfs(i); } res(i,1,m)num[be[i]]++; res(i,1,tot)ans+=num[i]-1; cout<<ans; return 0; }

反正能AC

李ys的神奇代码

但是标答或者说是更快的方法是李ys大神所用的并查集（Kruskal）就可以达到最快！！！

#include<iostream> #include<cstdio> #include<ctime> #include<algorithm> using namespace std; const int MAX=100000*4; int fa[MAX],ans,n,m; int findfa(int k) { if (fa[k]==k) return k; return fa[k]=findfa(fa[k]); } inline int read() { char x=(char)getchar(); int re=0; while (x<='9'&&x>='0') { re=re*10+x-48; x=getchar(); } return re; } int main() { freopen("heart.in","r",stdin); freopen("haert.out","w",stdout); n=read();m=read(); for (int i=1;i<=m;i++) fa[i]=i; for (int i=1;i<=n;i++) { int x=read(),y=read(); int f1=findfa(x); int f2=findfa(y); if (f1!=f2) { fa[f1]=f2; ans++; } } printf("%d",ans); return 0; }

第三题：题(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

题解

第三题： 第三题是第一题倒过来。 注意到对于任意两个非负整数A， B。 A and B + A or B = A + B 于是Bi+Ci = A1 + A2 + ….. + An + Ai * n 我们可以把所有数求和， 得到Ai的和， 记为sum， 再对每个数用Bi+Ci-sum / n 可以得到Ai 最后跑一遍第一题判定一下是否合法即可 值域在0到8191只是为了随机数据随出来B和C都在1e9以内， 没有实际意义

听小编一言，上诉都是渣渣！！！！！ 看小编的代码！！！！！

code（垃圾标程）

//#include <bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> using namespace std ; int n ; const int MAXN = 200010 ; typedef long long LL ; int B[MAXN], C[MAXN], a[MAXN]; LL b[MAXN], c[MAXN] ; struct Node { int b, c, id ; bool operator < (const Node ano) const { return b + c < ano.b + ano.c ; } } opt[MAXN] ; int cnt[MAXN] ; bool check(int x) { int now = x ; for (int i = 1; i <= n; i ++) { a[opt[i].id] = now ; now += ((opt[i + 1].b + opt[i + 1].c - opt[i].b - opt[i].c) / n) ; } memset(cnt, 0, sizeof cnt) ; memset(b, 0, sizeof b) ; memset(c, 0, sizeof c) ; for (int i = 1; i <= n; i ++) { for (int j = 0; j < 20; j ++) { if ((a[i] >> j) & 1) cnt[j] ++ ; } } for (int i = 1; i <= n; i ++) { for (int j = 0; j < 20; j ++) { if ((a[i] >> j) & 1) { b[i] += 1LL * cnt[j] * (1 << j) ; c[i] += 1LL * n * (1 << j) ; } else { c[i] += 1LL * cnt[j] * (1 << j) ; } } } return b[1] + c[1] >= B[1] + C[1] ; } bool check2(int x) { int now = x ; for (int i = 1; i <= n; i ++) { a[opt[i].id] = now ; now += ((opt[i + 1].b + opt[i + 1].c - opt[i].b - opt[i].c) / n) ; } memset(cnt, 0, sizeof cnt) ; memset(b, 0, sizeof b) ; memset(c, 0, sizeof c) ; for (int i = 1; i <= n; i ++) { for (int j = 0; j < 20; j ++) { if ((a[i] >> j) & 1) cnt[j] ++ ; } } for (int i = 1; i <= n; i ++) { for (int j = 0; j < 20; j ++) { if ((a[i] >> j) & 1) { b[i] += 1LL * cnt[j] * (1 << j) ; c[i] += 1LL * n * (1 << j) ; } else { c[i] += 1LL * cnt[j] * (1 << j) ; } } } for (int i = 1; i <= n; i ++) { if ((b[i] != B[i]) || (c[i] != C[i])) return 0 ; } return 1; } int main() { freopen("problem.in", "r", stdin) ; freopen("problem.out", "w", stdout) ; scanf("%d", &n) ; for (int i = 1; i <= n; i ++) scanf("%d", &opt[i].b), B[i] = opt[i].b, opt[i].id = i ; for (int i = 1; i <= n; i ++) scanf("%d", &opt[i].c), C[i] = opt[i].c ; sort(opt + 1, opt + n + 1) ; for (int i = 2; i <= n; i ++) { if ((opt[i].b + opt[i].c - opt[i - 1].b - opt[i - 1].c) % n != 0) { puts("-1") ; return 0 ; } } int l = 0, r = 8191 ; while (l < r) { int mid = (l + r) >> 1; if (check(mid) ) r = mid ; else l = mid + 1 ; } if (check2(l)) { for (int i = 1; i <= n; i ++) printf("%d%c", a[i], (i == n ? 10 : ' ')) ; } else puts("-1") ; }

xc大大的O（n）解法

A+B=A&B+A|B

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define name "problem" #define maxn 100009 typedef long long ll; using namespace std; ll b[maxn],c[maxn],a[maxn]; void get(ll &y) { y=0; char x=getchar(); while('0'>x||x>'9') x=getchar(); while('0'<=x&&x<='9') { y=y*10+x-'0'; x=getchar(); } } int main() { freopen(name".in","r",stdin); freopen(name".out","w",stdout); ll n; get(n); ll sum=0; for(int i=1;i<=n;i++) { get(b[i]); sum+=b[i]; } for(int i=1;i<=n;i++) { get(c[i]); sum+=c[i]; } if(sum%(2*n)==0) sum/=2*n; else { cout<<-1<<endl; return 0; } for(int i=1;i<=n;i++) { if((b[i]+c[i]-sum)%n==0) a[i]=(b[i]+c[i]-sum)/n; else { cout<<-1<<endl; return 0; } } for(int i=1;i<=n;i++) { cout<<a[i]<<(i==n ? "\n" : " "); } }

总结

今天也无力回天了…… 面对现实吧，小编自己只是个渣渣…………………… 然后预祝所有的OIer考试顺利！！！ （自己更加顺利！！！！！） （没有高精度！！！） （今天忘发图！！！）