CVBB ACM Team

题意:给定$n$，求最大的$gcd(a,b)$，其中$1 \leq a < b \leq n$。$(2 \leq n \leq 10^6)$

题解:我太菜了，去线性筛最小质因子。因为$a,b$不同，所以肯定要丢掉一个质因子，最小的质因子是$2$，因此只需要取$\lfloor{\frac{n}{2}}\rfloor$和$2 \cdot \lfloor{\frac{n}{2}}\rfloor$，答案为$\lfloor{\frac{n}{2}}\rfloor$。

题意:将$2n$个元素扔掉两个，剩下的两两一组，要求每组的和两两不互质，求分组方案。

题解:扔掉两个后一定可以让每组的和都是偶数。

题意:玩游戏。给定数字$n$，每次有下面两种操作，如果数字不为$1$可以$-1$，或除以一个不为$1$的奇数因数，两人轮流操作，无法操作的人输，问先手是否必胜。

题解:$n=1$直接输了，$n$为奇数直接变成$1$就赢了。如果$n$没有奇质因子，显然只能$-1$变成奇数就输了。否则如果有$1$个奇质因子，那么可以除掉这个奇质因子，如果结果是$2$就输了，否则就赢了；如果有多个奇质因子，可以人为操控除以一个奇因数使得结果是$2$和一个奇质因子的乘积，必胜。

题意:给定长度为$n$的序列，求一个长度为$k$的子序列，最大化$min(max(s_1, s_3, s_5, \ldots), max(s_2, s_4, s_6, \ldots))$。$(2 \leq k \leq n \leq 2 \cdot 10^5)$

题解:求最大的最小值，二分答案。分奇数位最大值是最小值和偶数位最大值是最小值两种情况，以奇数位为例，奇数位只能选$\ge mid$的值，偶数位随便选一个，而且必须选一个，最后看能不能选够$k$个即可。

题意:给定两个$01$串$s$和$t$，每次可以将$s$的一个子序列顺时针循环同构一次，问最少要多少次操作可以将$s$变成$t$，或判断无解。

题解:如果$01$数量不同则无解。否则每次操作相当于交替选择$s0t1$和$s1t0$的位置偶数次，并将相同位置的$s$和$t$变为一样。答案变为给定一个$01$串，选择最少的$01$交替且长度为偶数的子序列将其完全覆盖，设$f_{0,1}$为结尾$0,1$的子序列个数，dp扫一遍即可。

题意:交互题。给出一棵$n$个点的树，秘密选中两个点，需要猜出这两个点。每次可以询问任意数量的点，返回所有询问点中距离两个目标点距离之和最小的点，如果有多个点符合条件，随机返回一个。询问次数不能超过$14/11$。$(2 \le n \le 1000)$

题解:首先访问所有的点，得到两个目标点之间的距离$x$。然后我们二分两个点中更深那个点的深度，询问所有深度$>=mid$的点，看答案是否为$x$，二分过程中我们维护返回点中最深的点，这个点即为其中一个目标点，然后以这个点为根dfs一次，访问所有距离根$x$的点即可得到另一个点。这种方法一共需要$1+10+1=12$次。（这一次卡了一万年）我们忘记了利用第一次询问得到的那个点，我们可以以那个点为根再dfs一次，此时两个点中更深那个点的深度的范围为$[\frac{x}{2},x]$，$x$与$n$同阶，这样二分的次数可以减少一次，正好询问$11$次。