A. Spy Detected!

对于\(i \in [2, n -1]\)，当且仅当\(a_i \ne a_i - 1\)且\(a_i \ne a_{i + 1}\)时，\(i\)为最终答案。

否则，答案可能是\(1\)或者\(n\)，将\(a_1\)和\(a_n\)与\(a_2\)比较看那个与\(a_2\)相同，另一个就是答案。

B. Almost Rectangle

标记出两点的坐标\((x_1, y_1)\)，\((x_2, y_2)\)。

若两点不同行且不同列，那么已经确定了一个唯一的矩形。

若两点同属第\(x\)行，则只需再其他行种任选一行\(x^\prime\)，在\((x^\prime， y_1)\)和\((x^\prime， y_2)\)处加点即可。

同列的做法类似。

C. A-B Palindrome

首先，由于是回文串，有些?的位置填什么是已经确定了的。

统计字符串中，还需添加0的数量，还需添加1的数量，剩余?的数量，分别记为\(a, b, c\)。

那么如果\(c\)是偶数，那么\(a\)和\(b\)都必须是偶数。然后扫一遍，先填其中一种，再填另外一种。

如果\(c\)是奇数，那么，字符串的长度必须是奇数，\(a\)和\(b\)中必须有且只能有一个奇数，且字符串的中心为?。分类讨论，先填中心，转换成之前的情况处理。

D. Corrupted Array

其实\(b\)的顺序不会影响结果，为方便处理，不妨先将其升序排序。

假设\(x\)为\(b_i\)，\(sum = \sum_{i = 1}^{n + 2} b_i\)，那么\(\forall i \in [1, m -1]\)，若\(sum - b_i - b_{m + 2} = b_{m + 2}\)，则\(b\)除去\(b_i\)和\(b_{m + 2}\)就是一个可行解。

\(x\)也可能是\(b_{m + 2}\)，特判一下就可以了。

E. Permutation by Sum

\(p_l, \dots, p_r\)的顺序其实不影响结果，不妨假设其为升序。

枚举\(p_l\)的值，可以\(O(n)\)判断是否有可行解。总的时间复杂度为\(O(n^2)\)。

判断

不妨假设\(\forall i \in [l+1, r], p_i = p_{i-1} + 1\)。记此时\(\sum_{i = l}^r p_i = t\)

从右边开始处理，若\(t > s\)，则后续无论怎么搞，都无法满足条件。

若\(t < s\)，则可以放大当前元素。每次放大不能放大到超过\(s\)，也不能放大到违反升序的假设，即放大存在上界\(p_i + min(s - t, ma - p_i)\)。其中，\(ma\)表示第\(i\)个位置，不违反升序假设的最大值。

易得：每次尽可能放大是最优解之一。

然后模拟一下就完事了。

F. Education

假设最终Polycarp停在第\(i\)个位置。那么，对于之前的位置，能晋升就晋升是最优的。

贪心+模拟完事。

G. Short Task

由于要找满足条件的最小的\(n\)，所以对于一个因子集合，每个因子只出现一次是最佳的。

由此，除\(1\)和\(n\)本身外，可以只考虑素因子以及素因子的组合。

然后就是欧拉筛跑一下。

假设当前已经得到了\(d(n) = c\)，若加入一个新的素因子\(p\)，那么\(d(np) = c(p+1)\)。

假设当前已经得到了\(d(n) = c\)，若删除一个重复的素因子\(p\)，那么\(d(n) = c - pd(\frac{n}{p})\)。