上一次打cf还是好多年前，又开始研究生新的旅程，cf还是好好打打吧，毕竟不占太多时间，提高基础算法能力。这次只出了两题，而且速度偏慢。
A:Mahmoud and Ehab and the MEX
题意：给出一个非负集合S和一个数X，让你通过加数或者减数的方法使x成为加入S的最小数。
思路： 水，比x小的数多应该加上去，如果x在集合中，应该减掉。
B：Mahmoud and Ehab and the bipartiteness
题意：一棵树，可以划分为二分图，然后询问这个二分图最大还能添多少条边。
思路：树已经给出，那么我们可以通过dfs统计出两个集合A,B，然后不同集合之间才可能出现边，已经有了n-1条边,结果为size(A)*size(B)-n-1,注意爆int。
积累: dfs 遍历用图来处理，一般建图可以用两种方法，时间限制没那么紧的可以用vector来存储，时间限制比较紧的就必须要用链式前向星。
下面主要回顾链式前向星。
struct Edge
{
int next;//当前起点的下一条边
int to;//当前边的终点
int w;//当前边的参数
}edge[n*2];
辅助数组 head[]//每一个顶点出发的起始边，初始化时赋值为-1.
memset(head,-1,sizeof(head))
void add(int u,int v,int w)
{
for(int i=head[u];i!=-1;i=next[i])//判重
{
if(edge[i].to==v)
{
edge[i].w=min(edge[i].w,w);
return;
}
}
edge[cnt].w = w;
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
创建时初始化只要将 size 定为 0 ，head 数组全部赋值为 -1 即可，每加入一个结点，先记录该结点的 point 、 val 等信息，再记录下 nxt 信息，最后将 head 值改变，size ++ ；访问某个根 a 时首先访问 size 值等于 head [ a ] 的结点，即最后一个挂载上去的结点，然后依次访问 size 等于当前结点 nxt 值的结点，直到访问到 i 等于 -1 为止；
遍历方法：
在dfs中，用 for(int i=head[u];i!=-1;i=next[i]) { }
C:Mahmoud and Ehab and the xor
题意:给集合中数的个数n，和集合中所有值的按位异或值k，让你给出集合是否存在，并且进行举例,集合中的数小于1e6,x,n小于1e5
这道题做的时候在想通过统计每一位的奇偶性来处理，但也没想出什么可构造的方法能保证集合中的数都不同的性质。
题解思路：为了更好地找出普遍方案，我们可以从小的开始枚举，当n=1时，S={X},当n=2时，且x不为0时，S={X,0},当x为0时，S显然是不存在的，当n为3时，我们可以轻易写出很多组合，但由于我们一般性枚举都是在低位开始枚举的，所以我们尽量把组合放到高位，避免集合里出现重复数字，由于1e5<=217<=218<=1e6，所以我们枚举的数与2^17与一下，我们可以用这样的组合（（1<<17)|X),(1<<17)|(1<<18），1<<18)的组合。当n>3时，我们枚举可以在1开始枚举，这样结果不会和最后三个数重复。
D,E,F代补
网友评论