Codeforces Round #651 (Div. 2)
$1$到$n$中任选两个数字$a,b$，能够得到的最大$\gcd(a,b)$
题解：$\gcd(\lfloor\frac n 2 \rfloor,2·\lfloor\frac n 2 \rfloor)=\lfloor\frac n 2 \rfloor$
数组$a$大小为$2n$，先任选两个数字丢掉，再将其余数字两两一组变成二者的和化为大小$n-1$的数组$b$。要求使得数组$b$的最大公因数不为$1$。
题解：两奇数相加得偶数，两偶数相加还是偶数。只要使得奇、偶数数目为偶数个即可。故如果初始奇、偶数为偶数个，扔掉两奇数或两偶数；初始奇、偶数为奇数个，扔掉一奇一偶。最大公因数$2$
初始给出正整数$n$，两玩家轮流操作，每次可以选择在数字大于一的情况下减一或除以大于一的奇因子。无法操作者败
题解：分类讨论。
- $n$为奇数。除以它本身先手必胜（$1$是特例，必败）。
- $n$为偶数且没有大于一的奇因子。先手只能减一之后对方得到上一种局面必胜，故必败（$2$是特例，必胜）。
- $n$为偶数有大于一的奇因子。先手将奇因子除掉将第二种局面交给对方，故如果因子$2$个数不为一，先手必胜。而当因子$2$个数为一时，若奇因子个数为一，$2·p$减一变奇数必败，除以奇因子必败，总之必败；若奇因子个数不为一，可以除以部分奇因子将$2·p$的局面交给对方以获得必胜。
给定一个长度为$n$的数组$a$，可以选择长度为$k$的子序列（重新标号，从$1$开始），请最小化$\min(\max(s_1, s_3, s_5, \ldots), \max(s_2, s_4, s_6, \ldots))$。
题解：这个长得还挺二分的哦。check某个$\text{mid}$能否成立的时候，分成使得奇数位满足和使得偶数位满足两种，贪心地看能否凑够子序列长度。
给出长度为$n$的$01$字符串$s,t$，每次操作可以选一个子序列顺时针旋转，问最少几次从$s$变到$t$。
题解：能够变换成功当仅当两串为anagram。显然满足$s_i=t_i$的位置是不需要被考虑的。而观察发现剩余位置里每次旋转形如$\mathsf{01010101、101010}$的子序列是最优的，可以贪心地扫一遍详见代码。
交互。给出一棵$n(2 \le n \le 1000)$个节点的树，对方选定两个节点$s,f$给你猜。你可以做出若干询问，询问给出一个点集$a$，对方会提供点集中到$s,f$距离之和最小的点和这个距离。
easy version最多$14$问，hard version $11$问。
题解：我还挺喜欢这个题的，赛时wa了E看这个还挺有思路的，刚刚好写完，结果莫名其妙的wa了就结束了。后来发现是打错了某个地方的变量名，，，
首先可以想到，询问全部点，距离之和最小的只能是在$s$到$f$路径上，且距离之和是$d_0=dist(s,f)$，于是我们得到一个$sf$链上的点$x_0$。问题数量差不多是$\log n$级别的，于是想到二分。二分得到的$d_0$，每次dfs得到距离$x_0$为$mid$的点集询问，找出最远的使得$d=d_0$的距离及点$x_1$，则$x_1$是距离$x_0$较远一端的端点（得到答案之一）。之后再询问距离$x_1$为$d_0$的点集得到另一个答案$x_2$。
其间，二分区间如果是$[1,d_0]$可能会在二分过程中消耗$10$个问题，总问题数$12$过不了hard version。可以想到距离链上一点较远的点距离肯定大于链长之半，所以二分$[\frac {d_0} 2,d0]$可以恰控制在$11$次询问内。