A

赛时直到最后 10min 才做出这个 A 题，之前猜了一个结论一直没敢写，本来不抱啥希望 AC 的结果比赛结束时交了一发竟然 A 了，由此可见我的水平之菜/dk

考虑每次取出字符串开头字符，不妨设之为 \(c_1\)​​，以及字符串末尾的最靠后的不同于 \(c_1\)​​ 的字符，不妨设之为 \(c_2\)​​，设除了 \(c_1,c_2\)​​ 之外另一个字符为 \(c_3\)​​，我们就维护两个指针 \(l,r\)​，以及一个变量 \(cnt\)​ 表示目前跳了多少步，我们每次贪心地找到 \(l\)​ 后面下一个 \(c_1\)​，以及 \(r\)​ 前一个 \(c_2\)，然后分别令 \(l,r\) 为这两个位置，并令 \(cnt\) 加一，如此操作下去直到 \((l,r)\)​​ 中 \(c_3\) 个数 \(<cnt\) 即可，然后令这些元素组成一个子序列并将这些元素从序列中删去。

然鹅一个我不太能理解的地方是，为什么这样最少 6 个子序列就能划分整个字符串 \(S\)，赛时的想法是可能与每组 \((c_1,c_2,c_3)\) 最多出现一次有关，但是这个结论显然是错误的，并且貌似官方题解也并没有采用上文所述的做法。有哪位好心的鸽鸽能给个证明，或者能给组 hack 数据把上面的做法叉掉啊/kel

B

赛时没有想出来，甚至连最起码的思路也没有，说明我还是不太适合做这样的思维题啊/kk

考虑将 \(S\) 第一个位置上的字符加 \(2\)（即，A 变成 C，B 变成 A，C 变成 B），第二个位置上的字符加 \(1\)，第三个位置上的字符加 \(0\)，第四个位置上的字符加 \(2\)，第五个位置上的字符加 \(1\)，以此类推，那么不难发现，每次操作等价于将一段长度为 \(3\) 的，且三个字符完全相同的连续段全部变成任意一种字符，那么我们考虑这样的过程：我们从左往右遍历 \(S\) 的每一个字符，并维护一个栈存储当前没有被消除完毕的字符，每次往栈顶加入当前遍历到的字符，如果栈顶三个字符全部相同则将这三个字符直接弹出栈，那么可以发现，我们弹出栈的那些字符是可以*搭配成连续段插入序列的任何一个位置的，而我们没有弹出栈，也就是栈中剩下的那些字符——它们的相对顺序是不会发生变化的，因此我们考虑对 \(S,T\) 都执行一遍上面的操作，然后检验 \(S,T\) 匹配完以后栈中的元素是否相同即可。

时间复杂度 \(\Theta(n)\)。

C

一道挺有意思的数数题，赛时 115min 刚出来还是挺有成就感的（

首先一个显然的事实是，\(A\) 数组中最多只有两种不同的元素，如果 \(A\) 中有两种不同的元素，那么较大者必然是原序列的 LIS。

特判掉 \(A\)​ 中只有一种元素的情况，打个表可以发现 \(A\)​ 中只有一种元素的情况符合条件，当且仅当 \(A\)​ 中唯一的元素 \(\le\lfloor\dfrac{m}{2}\rfloor\)，或者等于 \(n-1\)。

我们假设 \(P\) 中 LIS 的长度为 \(l\)，那么不难发现，\(A\) 中等于 \(l-1\) 的位置都是 \(P\) 所有 LIS 的必经之点，因此我们可以将原题面中每个元素都 \(\le m\) 序列计数问题转化为 01 序列计数问题，其中一个位置是 \(1\) 当且仅当它是 LIS 的必经之点，否则表明它不是 LIS 的必经之点。

考虑什么样的 01 序列符合要求，打个表可以发现，一个 01 序列符合要求，当且仅当它 \(1\)​ 的个数 \(c_1\le l\)​，并且我们把它所有 \(0\)​ 的连续段提取出来，设它们的长度为 \(L_1,L_2,L_3,\cdots,L_k\)​，满足 \(c_1+\sum\limits_{i=1}^k\lfloor\dfrac{L_i}{2}\rfloor\ge l\)​，比较感性的证明大概就，我们对所有连续的 \(0\)​ 段的相邻元素两两配对，然后用类似于阶梯状的方式在这些相邻元素上填数，然后对于那些落单的元素就从 \(n\)​ 开始从大往小填，比如 \(01\)​ 序列 \(100000100010\)​ 就对应序列 \([1,3,2,5,4,12,6,8,7,11,10,9]\)，不难发现这样可以使原序列的 LIS 达到最大值，如果要求的 LIS 比这还大就办不到了。

因此我们枚举 01 序列中有多少个 \(1\)​，以及有多少个落单的 \(0\)​，设它们分别为 \(i,j\)​，那么显然就有 \(c_1+\sum\limits_{i=1}^k\lfloor\dfrac{L_i}{2}\rfloor=i+\dfrac{n-i-j}{2}\)​，故 \(l\)​ 的范围就是 \([\max(i,3),\min(i+\dfrac{n-i-j}{2},m)]\)​，然后考虑怎样排列这个 01 序列，首先将落单的 0 插入 \(i\)​ 个 \(1\)​ 组成的 \(i+1\)​ 个缝隙的方案数为 \(\dbinom{i+1}{j}\)​，将剩余 \(\dfrac{n-i-j}{2}\)​ 组配好对的 \(00\)​ 插入 \(i+1\)​ 个空隙的方案数为 \(\dbinom{\dfrac{n-i-j}{2}+i}{i}\)​，因此 \(A\)​ 中有两个不同元素的部分的答案可以写成：

\[\sum\limits_{n-i-j\equiv 0\pmod{2}}\dbinom{i+1}{j}\dbinom{\dfrac{n-i-j}{2}+i}{i}·\max(\min(i+\dfrac{n-i-j}{2},m)-\max(i,3)+1,0) \]

看看这个式子，是不是很简单啊（大雾

\(\Theta(n^2)\) 计算即可。

D

一道神仙找性质题。

开始翻译官方题解（bushi

首先抛出结论：如果设 \(M_{AB}\) 为 \(S\) 所有前缀中 B 数量减 A 数量的最大值，\(M_{BC},M_{CA}\) 同理，那么一个序列 \(S\) 符合条件，当且仅当 \(M_{AB}+M_{BC}+M_{CA}\le n\)。

必要性：我们记 ABC,BCA,CAB 的数量分别为 \(A,B,C\)，那么我们发现，当我们放入一个 ABC 或 CAB，只会导致某些前缀的 B 数量减去 A 数量减少，只有我们放入 BCA 时才会使该值增加，因此 \(M_{AB}\le B\)，同理 \(M_{BC}\le C,M_{CA}\le A\)，三者加起来可得到 \(M_{AB}+M_{BC}+M_{CA}\le n\)。

充分性：我们考虑求出第 \(i\) 个 A,B,C 所在的位置（\(i\in[1,n]\)），那么我们这样构造：第 \(i\) 个 A 匹配第 \(i+M_{AB}\) 个 B 以及第 \(i+M_{AB}+M_{BC}\) 个 C（如果超过了 \(n\) 则自动减去 \(n\)，即第 \(i+n\) 个 X 即为第 \(i\) 个 X，\(X\in\{A,B,C\}\)）。首先显然匹配的这些位置互不相同，而根据 \(M_{AB}\) 的定义有，如果我们把 \(S\) 重复写三遍，那么第 \(i\) 个 \(A\) 的位置必然前于第 \(i+M_{AB}\) 个 B），也就是说第 \(i\) 个 A 的位置早于第 \(i+M_{AB}\) 个 B 的位置，早于第 \(i+M_{AB}+M_{BC}\) 个 C 的位置，早于第 \(i+M_{AB}+M_{BC}+M_{CA}\) 个 A 的位置，而根据 \(M_{AB}+M_{BC}+M_{CA}\le n\) 可知，第 \(i+M_{AB}+M_{BC}+M_{CA}\) 在环上的位置前于第 \(i\) 个 A，也就是我们钦定的三个位置刚好顺着组成了 ABC，对应到序列上也就是 ABC,BCA,CAB 的一种。

因此我们可以写出这样一个 \(n^6\) 的 DP：\(dp_{a,b,c,AB,BC,CA}\) 表示目前有 \(a\) 个 A，\(b\) 个 B，\(c\) 个 C，目前 \(M_{AB},M_{BC},M_{CA}\) 分别是 \(AB,BC,CA\)，有多少个符合条件的序列，转移可以做到 \(\Theta(1)\)，因此总复杂度就是 \(\Theta(n^6)\)。