CVBB ACM Team

题意:每次可以对$a$乘以$2,4,8$或者在整除的情况下除以$2,4,8$，问最少多少步可以变成$b$或判断无解。

题解:不妨设$a \le b$，那么如果有解必须满足$a|b$而且$\frac{b}{a}$是$2$的次幂，然后只需要对$8,4,2$分别试除即可。

题意:给出一个$n$个元素的集合$s$，求最小的正整数$k$使得所有元素异或$k$组成的新集合和原集合相同，或判断无解。$(1 \leq n \leq 1024, 0 \leq s_i < 1024)$

题解:数据范围很小，暴力枚举$1$到$2047$即可。

题意:求$\sum_{i=1}^{n}{\text{pop_count}(i \oplus (i-1))}$。$(1 \leq n \leq 10^{18})$

题解:设$f(n)=\sum_{i=1}^{n}{\text{pop_count}(i \oplus (i-1))}$，有递推式$f(n)=2f(2^{i-1})+1+f(n-2^i)$，其中$2^i$是$n$的最高位$1$对应的次幂，边界为$f(0)=0$。

题意:$n$个博客和$n$个主题，按照顺序写这$n$个博客，每个博客和其它一些博客会有一些联系，每个博客的主题就是所有与它有联系且已经写过的主题的$mex$。现在给定每个博客希望写哪个主题，问是否存在一个写博客的顺序使得这个条件满足。

题解:建图，根据目标主题从小到大以此考虑每个博客，相同主题的顺序无所谓，因为显然它们如果不相互独立一定无解。然后每写一个博客更新所有与它相连的博客的$mex$值，只需要维护每个点现在$mex$是多少，然后一但中断就不更新即可。中途如果某个博客的主题与题目给出的不符即无解，否则有解。

题意:给出$n$个数，每个数形如$p^{k_i}$，将这些数分为两组，使得两组内各自数字的和的差的绝对值最小。

题解:从高位开始贪心，如果$k_i$次有偶数个数，那么直接贪心分即可，否则肯定会多出来一个，那么之后的所有数就要分到另一组来尽力弥补这一个带来的差值。记录一下要多少个才能弥补，一旦发现需要的数量超过剩余的数量，就直接后面的数分给另一组即可。

题意:读错题了想了一万年。现在有$n$个项链，每个项链由两个数字$a,b$组成，这两个数字之间相连。每个数字需要再额外和另外一个数字相连，使得所有项链组成一个环。整个环的权值由所有你自己连的边两侧的数字决定，设每一组的两个数字是$x,y$，设$2^k$是最大能整除$x \oplus y$的$2$的次幂，那么权值为$k$，如果$x \oplus y = 0$，那么权值为$20$。整个环的权值是每一组权值的最小值，求最大权值。$(1 \leq n \leq 5 \cdot 10^5, 0 \leq a, b < 2^{20})$

题解:因为$k$很小，我们可以直接枚举这个$k$。如果$x \mod 2^k = y \mod 2^k$，等价于$x \oplus y$的权值$\le k$，因此可以由$x$向$x \mod 2^k$连边，然后判是否存在欧拉回路然后找出一条欧拉回路即可。注意欧拉回路除了要求每个点的度数是偶数还要求图是要联通的，在使用Hierholzer算法时开个数组记录每个点跑到哪条边了，就可以实现删边操作。