A. Simple Palindrome

题意：给定正整数n(1≤n≤100)，输出任意一个长度为n、仅由aeiou组成且使得回文子序列的数量尽可能少的字符串。（回文是指一个字符串从左数任意一个字母和从右数相同次序的字母相同；子序列是通过删除原序列中若干项得到的，可以等于原序列，也可以为空）

题解：构造一个形如aaaeeeiiiooouuu的字符串，且第i种字母的数量为，设n除以5得余数x，则前x种字母的ti为1，后面ti为0即可满足题意。

正确性证明：首先发现当五个元音字母在字符串中的数量确定时（设为a1~a5），由于仅由一种字母组成的子序列一定是回文的，回文子序列的数量至少是，而且只要把所有相同字母放一块，就不可能产生更多的回文子序列，因此问题转换成了如何分配五种字母的数量使回文子序列最少。然后发现当其中一种字母比另一种字母的数量多m≥2时， 

将多的字母的数量给少的字母1，将产生更少的回文子序列，那么最终任何一种分配方式都能够导向某个五种字母之间的数量最多差1的情形，也就是任意一种m≥2的分配方式都会比某个m≤1的方式差，而任意一种数量最多差1的分配必然是(n%5)种多1的和(5-n%5)种少1的，回文子序列的数量是一个定值，因此构造一个这样的字符串就能达到最少。

Code：

B2. The Strict Teacher (Hard Version)

题意：教室里有n(3≤n≤1e9)张桌子排成一排，m(1≤m≤1e5)个老师和戴维上演一场猫抓老鼠的戏，一开始所有人都在某张桌子旁（各不相同），每个人每回合能移动到旁边的某个桌子，或者不动，且每个回合戴维先移动，然后所有老师移动。有q(1≤q≤1e5)次询问，每次给定戴维的初始位置，问所有人在最优行动的情况下，多少回合之后戴维会被老师抓住？（戴维和某个老师在同一张桌子时被抓住，老师希望尽快抓住戴维，戴维希望尽可能迟被抓住）（n，m，m个老师的初始位置以及q和q次询问戴维的初始位置是给定数据，简单版本中m=2，q=1）

题解：因为戴维是先手移动且和老师的速度是一样的，因此只要老师的包围圈还有空间，戴维就不会被抓住，计算初始时戴维所在的包围圈有多大，再除以包围圈缩小速度（1或2）向上取整就是答案。这里使用set保存老师的位置，查找最近的老师的位置的复杂度为log(m)（也可以将保存的位置排序，然后二分查找），最终的复杂度是O((m+q)·log(m))。

Code：

C. Lazy Narek

题意：有n个长度为m的仅由26种小写字母组成的字符串(1≤n,m≤1000)，依次为s1~sn，从这个字符串的序列中找一个子序列（子序列的定义在A题说了），将子序列中的字符串按顺序拼起来成为一个新的字符串t，然后Narek开始从t中从左到右寻找子序列“narek”，先找字母n，找到n之后找a，找到a之后找r...每当组成一个“narek”，Narek会加5分，然后从最后找到字母k的位置继续找下一个“narek”，当Narek结束寻找以后，t中每一个没有为Narek加分的n、a、r、e、k都将使Narek减1分，那么总的得分将是一个关于t的函数，问Narek最多能得到多少分？（其中n、m和n个字符串是给定的数据）

题解：上dp！定义一个子问题(i,j)为：仅有前i个字符串，且Narek到最后在找的字母是“narek”中的第j+1个时，Narek最多能得到多少分。记子问题(i,j)的答案为ans(i,j)，并使用-inf用于标记无效的答案，初始时ans(0,0)=0，其他所有ans(i,j)都是-inf。

    每当新增第i个字符串，对于j=0~4，都有将si拼接在子问题(i-1,j)的最优串的最后或者不拼接两种可能：

    如果ans(i-1,j)不为-inf，则ans(i,x)更新为max(ans(i,x),ans(i-1,j)+score)，其中x是在最优串后面拼接si之后当前在找的字母的次序（减1），score是拼接si所新增的分数（可能为负）。

    如果ans(i-1,j)不为-inf，则ans(i,j)更新为max(ans(i,j),ans(i-1,j))。

    如此就从仅有前i-1个字符串时的最优结果推导到了有前i个字符串的最优结果，最后答案就是ans(n,0)~ans(n,4)当中的最大值。其中新增分数score的计算有点神奇，每次碰到“narek”中的某个字母就-1，而如果匹配完了一组应该+10。

Code：

D. Alter the GCD

题意：有两个长度为n的数组a和b（1≤n≤2e5，1≤ai,bi≤1e9），你可以选定一个区间[L,R]（1≤L≤R≤n），对于所有在区间内的下标i，交换ai和bi。问交换元素之后的gcd(a)+gcd(b)能达到的最大值是多少，以及有多少种[L,R]能达到这个最大值？（n和a、b是给定数据，gcd(a)是指a当中所有数字的最大公因数）

题解：使用分治法，通过两个相邻的区间上的答案推导合并区间上的答案，从长度为1的区间开始一直合并到最终的区间[1,n]。区间合并时需要考虑三个答案的合并：L和R都在左子区间[u,mid]的答案、L和R都在右子区间[mid+1,v]的答案，以及L在左子区间而R在右子区间的答案（答案是由最大值和数量组成的二元组）

    前两种情况可以先假设已经求出来了，对于第三种情况，令L从mid向左枚举至u，根据gcd的一个性质[1]，gcd(gcda(1,L-1),gcdb(L,mid))和gcd(gcdb(1,L-1),gcda(L,mid))两个gcd组成的二元组将至多有log(v-u)量级的不同值，将这些不同的二元组保存下来（两个gcd分别对应交换元素后的gcda(1,mid)和gcdb(1,mid)），令R从mid+1向右枚举至v，同理保存一些不同的二元组（对应交换后的gcda(mid+1,n)和gcdb(mid+1,n)），然后让两堆二元组一一组合就能计算出当前情况的答案了。

    两个答案的合并就是如果最大值相同，则数量相加，否则等于最大值大的那个。另外这个算法好像快到O(n·(logn)^3)了啊，甚至没算gcd的复杂度，居然能过，还是官方题解的思路，原本从可爱呜米酱偷师的算法也是这个复杂度最后被人hack了

    [1]一个长度为n的数组的前缀gcd将最多有log(n)种不同的值，因为每次变化都将是除以一个至少是2的数字。

Code：

E2. Subtangle Game (Hard Version)

题意：给定一个长度为L的数组a和一个n行m列的矩阵b（1≤L,n,m≤1500，1≤ai≤n·m，1≤bij≤n·m），Tsovak和Narek将在a和b上进行一场游戏，奇数轮为Tsovak行动，偶数轮为Narek行动（从1开始计数），第i轮由当前玩家从b当中选择一个与ai相等的数字bxy，如果选不了了则对手赢了（i>L或者b中没有与ai相等的数字了），否则将b缩减为从b(x+1,y+1)到b(n,m)的子矩阵，两位玩家都将以最优的方式行动，问最后谁赢了？（L、n、m以及a中的数字、b中的数字都是给定的，简单版本中L,n,m最大是300，且a和b中的数字不大于min(7,n·m)）

题解：首先对于任一玩家来说，如果当前有两个不同的选择b(x1,y1)和b(x2,y2)而x1≤y1且x2≤y2，那么选择b(x2,y2)总是会更好的，因为选择(x1,y1)之后对方可以选的位置将完全包含选择(x2,y2)之后对方可选的位置，对对方来说是多了赢的可能性，因此可以排除掉这些类似于(x1,y1)的选项，此后每回合每一行最多有一个选项，共有最多n个可选项，那么现在得到了L个选项列表，对应了每一步可以选的最多n个选项。

    接下来从第L个列表开始（之后简记为列表L），如果列表L-1中的某些选项对应的子矩阵包含了列表L中的任一选项p，若p已经在之前的回合被选择过，那列表L-1中子矩阵包含p的选项自然也不能选了，若p还未被选择过，列表L-1中子矩阵包含p的选项将导致L-1轮的玩家输掉游戏，因此可以将这些选项从列表L-1中删除，此时列表L-1中剩下的选项是使L-1轮的玩家赢的，接下来同理可以考虑列表L-2中的选项，若包含列表L-1中的任意选项就可以删掉，直到删掉第一个列表中的一些选项以后，如果还有剩余则Tsovak能赢，否则Narek赢。

Code：

    有史以来写的最长的专栏了（其实相比上一篇就是多贴了代码而已哈哈），喜欢记得点个赞儿再走吧！！