√\color{green}√：vp 时独立做出。

√\color{orange}√：vp 后独立做出。

√\color{red}√：经过提示后做出。

−\color{gray}-：未做出。

×\color{red}×：尝试提交过，未做出。

A

√\color{red}√，*900。

《开幕雷击》，vp 的时候被这糖题卡了。

考虑到同一种字母构成的子序列带来的贡献无论如何都无法去除，贪心地尽量让同一种字母放在一块即可；同时每种字母的数量应尽量平均，所以直接先将每种字符添加 ⌊n5⌋\lfloor \frac{n}{5}\rfloor 个，再将剩余的 nmod  5n\mod 5 个字母添加进来即可。

B1

√\color{green}√，*1000。

简单版本，n=2n=2。设 min⁡(b0,b1)=l\min(b_0,b_1)=l，max⁡(b0,b1)=r\max(b_0,b_1)=r。

分类讨论：

  • 当 a<la<l 时，学生会被在 ll 处的老师抓到，此时最优策略一直往左跑到 11，答案为 l−1l-1。
  • 当 a>ra>r 时同理，答案为 n−rn-r。
  • 当 l≤a≤rl\leq a\leq r 时，学生的策略是向中间跑。设 m=⌊l+r2⌋m=\lfloor \frac{l+r}{2}\rfloor，答案为 min⁡(m−l,r−m)\min(m-l,r-m)。

B2

√\color{green}√，*1200。

策略跟原来一样，排序后加个二分每次询问找到找到 l,rl,r 的值即可。

C

√\color{green}√，*1800。

发现选字符串的过程对之前的选择是无后效性的，考虑 dp。设 fi,jf_{i,j} 为当前选择到第 ii 个字符串，前面的选择为当前贡献了 narek 中的前 jj 个字符。

不选第 ii 个字符串的转移是 fi−1,j→fi,jf_{i-1,j}\rightarrow f_{i,j}，若选中第 ii 个字符串，假设 j=2j=2，前面贡献了 na 两个字符，则能带来贡献的子序列一定形如 reknareknarek...nar，扫一遍字符串，统计出能匹配上的子序列长度 xx 和末尾剩下的字符数量 ww，则有转移 fi,j+x−(m−x)→fi,j+wmod  5f_{i,j}+x-(m-x)\rightarrow f_{i,j+w \mod 5}。

最终答案则为 max⁡i=04{fn,i−i}\max^4_{i=0}\{f_{n,i}-i\}，注意 −i-i 是因为最后一次未匹配到的字符是不计入得分的。

D

−\color{gray}-，*2400。

困难啊，明明刚学过序列分治还是一点思路没有。

先用 st 表预处理 gcd，然后进行序列分治，函数 solve⁡(l,r)\operatorname{solve}(l,r) 返回的是对于所有被区间 [l,r][l,r] 包含的操作中能达到的最大答案与达成该答案的方案数。

操作一段区间相当于留下一段前缀 gcd 和一段后缀，由于 gcd 的性质，不同的前 / 后缀 gcd 个数最多只有 log⁡\log 个。

于是在序列分治的过程中，我们对左右两边分别统计，枚举（如图所示的）红 / 蓝色段的分界点，用一个二元组 (x,y)(x,y) 代表“在左 / 右侧，红色段的 gcd 为 xx，蓝色段的 gcd 为 yy”。用两个 map 记录左 / 右侧每个 (x,y)(x,y) 出现的次数，由于前面提到的性质，这样的二元组总共最多有 log⁡2\log^2 个。

处理完之后，我们二重循环枚举左右两个 map 中的二元组 (x0,y0)(x_0,y_0) 和 (x1,y1)(x_1,y_1)，把它们拼在一起，最后结果即为 gcd⁡(x0,x1)+gcd⁡(y0,y1)\gcd(x_0,x_1)+\gcd(y_0,y_1)，正常更新答案即可。

这样做的时间复杂度实际上是 nlog⁡2nn\log^2 n 而非 log⁡3\log^3，由两部分组成：更新 map 的复杂度就是正常序列分治的 nlog⁡nn\log n 乘以查询 gcd⁡\gcd 的 log⁡n\log n，而枚举二元组的部分由于序列一共只会被划分成 O(n)\mathcal{O}(n) 个区间，最多枚举 log⁡2\log^2 种两个二元组的组合，复杂度同样是 nlog⁡2nn\log^2 n。

E1

√\color{orange}√，*2100。

vp 的时候没时间写了，感觉挺简单的。

简单版的数据范围比较小，可以考虑直接暴力 dp，设 fx,i,jf_{x,i,j} 代表当前要获取的元素是 aia_i 且呆在 (i,j)(i,j) 处时是必胜还是必败。首先若 bi,j≠axb_{i,j}\neq a_x 一定必败。否则，由 SG 函数可知，当且仅当当前状态能走到的后继状态全都是必败状态，这个状态才是必胜状态。于是按游戏规则可得 fx,i,j=[∑i<i′≤n,j<j′≤mfx+1,i′,j′=0]f_{x,i,j}=[\sum_{i<i'\leq n,j<j'\leq m} f_{x+1,i',j'}=0]。直接转移是 O(n2m2l)\mathcal{O}(n^2m^2l) 的，每次求一遍二维前缀和优化一下，实现 O(1)\mathcal{O}(1) 转移即可。初始状态为 fl,i,j=[bi,j=ai]f_{l,i,j}=[b_{i,j}=a_i]，时间复杂度 O(nml)\mathcal{O}(nml)。

E2

咕咕咕。