这次比赛打得很舒服，莫名得了个Rank41，涨了219的Rating，就比较优秀。不过还是没有闫神厉害啊。
题目链接：:P。
【A】MEX
题意：
Evil博士把Mahmoud和Ehab绑架到了邪恶之地，因为他们在邪恶信息学奥林匹克竞赛(EOI)中取得了优异的成绩。博士想让他们回答一些问题后才放他们走。
Evil博士对集合很感兴趣，他有一个n个非负整数的集合。如果一个集合的MEX正好等于x，那么博士认为这个集合是邪恶的。
一个非负整数集合的MEX就是最小的不属于集合的非负整数。
Evil博士想要让他的集合变得邪恶，他每次可以做一个操作：往集合中添加一个非负整数或删除集合中的某个元素。
他最少做几次操作在能让这个集合变得邪恶呢？
输入：
第一行，两个数\(n,x(1\leq n\leq100,0\leq x\leq100)\)。
第二行，\(n\)个非负整数\(a_{1},a_{2},\cdots,a_{n}\)，表示集合中的元素\((0\leq a_{i}\leq100)\)。
输出：
一个数，表示最小操作数。
题解：
添加所有不在集合中的小于\(x\)的非负整数，如果\(x\)在集合中，删除\(x\)。
#include<cstdio>
int n,x,a[],less,ans;
int main(){
scanf("%d%d",&n,&x);
for(int i=;i<=n;++i){
scanf("%d",a+i);
if(a[i]<x) ++less;
if(a[i]==x) ++ans;
}
printf("%d",ans+x-less);
return ;
}
【B】二分图
题意：
Mahmoud和Ehab继续他们的旅程！在邪恶之地，众人皆知，Evil博士很喜欢二分图，特别是树。
Evil博士给定了一棵树，他想在树中加入尽量多条边，使得新图还是二分图。
求出最多添加的边数。
输入：
第一行，一个数\(n(1\leq n\leq10^5)\)，表示树的顶点数。
接下来\(n-1\)行，每行两个数\(u_i,v_i(1\leq u_i,v_i\leq n)\)，表示\(u_i,v_i\)间有连边。
输出：
一个整数，表示最多添加的边数。
题解：
黑白染色，答案=黑色点*白色点-(n-1)。
#include<cstdio>
int n,h[],nxt[],to[],tot=,vis[],sums[];
inline void ins(int x,int y){nxt[++tot]=h[x];to[tot]=y;h[x]=tot;}
void dfs(int u,int t){
vis[u]=;
++sums[t];
for(int i=h[u];i;i=nxt[i]){
if(!vis[to[i]]){
dfs(to[i],t^);
}
}
}
int main(){
int x,y;
scanf("%d",&n);
for(int i=;i<n;++i) scanf("%d%d",&x,&y), ins(x,y), ins(y,x);
dfs(,);
printf("%I64d",1ll*sums[]*sums[]-n+);
return ;
}
【C】异或
题意：
Mahmoud和Ehab到达了第三站。你知道，Evil博士喜欢集合，不过这次，Evil博士不会展出任何他的集合，而是让他们创造一个新的集合，丰富自己的集合收藏。
Evil博士有着他喜欢的邪恶数字\(x\)，他想让你创造一个包含\(n\)个不同的非负整数集合，使得这其中的数的异或和恰好等于\(x\)。集合中的数不大于\(10^6\)。
输入：
两个数，\(n,x(1\leq n\leq10^5,0\leq x\leq10^5)\)。
输出：
如果能创造这样的集合，先输出YES，然后输出一行\(n\)个互不相同的非负整数，表示集合，这些数不应该超过\(10^6\)。如果不能，输出NO。
题解：
当\(n=1\)时，输出\(x\)即可。
当\(n=2\)时，若\(x=0\)，无解；否则输出\(0\;x\)。
当\(n=3\)时，若\(x=0\)，输出\(1\;2\;3\)；当\(x=1\)，输出\(0\;2\;3\)；当\(x>1\)，输出\(0\;1\;x\oplus1\)。
当\(n>3\)时，先输出前\(n-3\)个非负整数，计算剩余的数，记为\(x_0\)。
接下来当做\(n=3\)的情况，不过输出的数要分别加上\(2^{17},2^{18},2^{17}+2^{18}\)。
#include<cstdio>
int a,b;
int main(){
scanf("%d%d",&a,&b);
if(a==&&b==) {puts("NO"); return ;}
puts("YES");
if(a==) {printf("%d",b); return ;}
if(a==) {printf("0 %d",b); return ;}
if(a==) {if(b==) printf("1 2 3"); else if(b==) printf("0 2 3"); else printf("0 1 %d",b^); return ;}
for(int i=;i<=a-;++i){
printf("%d ",i); b^=i;
}
if(b==) printf("%d %d %d",+((<<)+(<<)),+(<<),+(<<));
else if(b==) printf("%d %d %d",(<<)+(<<),+(<<),+(<<));
else printf("%d %d %d",(<<)+(<<),+(<<),(b^)+(<<));
return ;
}
【D】01字串
交互题不会做XD。
【E】函数
题意：
Evil博士对数学和函数很感兴趣。
他给出了两个数组\(a_{1},\cdots,a_{n}\)和\(b_{1},\cdots,b_{m}(m\geq n)\)。
他又对满足\(0\leq j\leq m-n\)的\(j\)定义\(c_{i}=a_{i}-b_{i+j}\)和函数\(f(j)=|c_{1}-c_{2}+c_{3}-c_{4}\cdots c_{n}|\)。
也就是\(f(j)=|\sum_{i=1}^{n}(-1)^{i-1}*(a_{i}-b_{i+j})|\)。
Evil博士想要Mahmoud和Ehab去计算\(f(j)\)的最小值。他发现这太简单了。
于是他加入了\(q\)个操作，第\(i\)个操作对\(a\)数组中的\([l_i,r_i]\)段加上一个数\(x_i\)。然后再让他们计算这个函数的最小值。
题解：
简化算式：\(f(j)=|\sum_{i=1}^{n}(-1)^{i-1}*a_{i}+\sum_{i=1}^{n}(-1)^{i-1}*b_{i+j}|\)。
记第一个\(\sum\)的结果为\(Sum\)。记第二个\(\sum\)的结果为\(S_{j}\)。那么在操作间，\(Sum\)的值会改变。
改变的数值容易计算，可发现，这样交错相加减的算式，\(Sum\)这样变化：\(Sum \to Sum+x_{i}(r_{i}mod\:2-(l_{i}-1)mod\:2)\)。
而对于\(S_j\)的值，因为被绝对值包着，我们需要让\(S_j\)尽量接近\(-Sum\)。
因为\(b\)数组不会改变，故\(S_j\)也不会改变，将\(S_j\)排序后，二分查找即可。
#include<cstdio>
#include<algorithm>
const int INF=99999999999999999ll;
int n,m,q,mj;
long long a[],b[],c[],sum;
long long Abs(long long x){return x<?-x:x;}
int main(){
scanf("%d%d%d",&n,&m,&q); mj=m-n;
for(int i=,f=;i<=n;++i,f^=) scanf("%I64d",a+i),sum+=f?a[i]:-a[i];
for(int i=;i<=m;++i) scanf("%I64d",b+i);
for(int i=,f=;i<=n;++i,f^=) c[]+=f?b[i]:-b[i];
for(int i=;i<=mj;++i) c[i]=-c[i-]-b[i]+((n&)?-b[i+n]:b[i+n]);
std::sort(c,c+mj+);
int l,r,x,len,mid;
long long ans;
l=, r=mj, ans=INF;
while(l<=r){
mid=(l+r)>>;
if(c[mid]<-sum) l=mid+;
else r=mid-;
if(Abs(c[mid]+sum)<ans) ans=Abs(c[mid]+sum);
}
printf("%I64d\n",ans);
for(int i=;i<=q;++i){
scanf("%d%d%d",&l,&r,&x);
len=r-l+;
if(len&) sum+=(l&)?x:-x;
l=, r=mj, ans=INF;
while(l<=r){
mid=(l+r)>>;
if(c[mid]<-sum) l=mid+;
else r=mid-;
if(Abs(c[mid]+sum)<ans) ans=Abs(c[mid]+sum);
}
printf("%I64d\n",ans);
}
return ;
}