AGC 054 (A~E) 题解
A
- 若\(s_0\neq s_1\)则，答案为\(1\)。
- 若存在\(i\)，满足\(s_i\neq s_0\and s_{i+1}\neq s_0\)，则答案为\(2\)。
- 否则答案为\(3\)。
B
首先一个合法分组和一个排列有着一一对应关系，所以只需要统计有多少分组。
然后乘上两边数量的阶乘即可。
C
首先考虑如何操作数最小。
一定是任意选择一个位置其中有\(>k\)个在他前面比他大的数。
然后将他往前移动，直到恰好有\(k\)个比他大的在他前面。
可以发现这样的排列是确定的。
dp的时候只需要从前往后dp，考虑把前面的数往后带。
其中一个数能往后带的条件是1. 恰好有\(k\)个比他大的在前面 2. 后面一个比他大。
然后往后带的数会放到一些不往后带的数的后面。
时间复杂度为\(O(N^2)\)。
D
首先\(o,x\)之间的相对位置不变。
\(()\)一定是按照最优匹配（与\(ox\)无关）。
所以可以考虑\(dp\)，转移的贡献为逆序对数。
E
假设\(a_1<a_n\)
一个数列是好的，当且仅当存在一个位置\(i\)，满足\(a_i\leq a_1\and a_{i+1}\geq a_n\)。
证明：
考虑倒着归纳，首先初始一定是\(x,y(x<y)\)，满足条件。
对于一个满足条件的序列如果插入元素的位置\(\leq i\or > i+1\)则不影响，否则在\(i,i+1\)中间一定任然满足条件。
考虑不满足上述条件的序列个数。
可以把数从小到大填。
设结尾是\(A+k\)，假设\(k\geq 2\)。
-
填入\(A+1...A+k-1\)，有\((k-1)!\)个方案。
-
填入\(1...A-1\)，有\(\frac{(A+k-3)!}{(k-2)!}\)个方案。
-
填入\(A+k+1...N\)，其中不能在某一个\([1...A]\)的右边，有\(\frac{(N-A-2)!}{(k-2)!}\)
总共\((A+k-3)!(N-A-2)!(k-1)/(k-2)!\)
答案即为\(\sum_{2\leq k\leq N-A} (A+k-3)!(N-A-2)!(k-1)/(k-2)!=(N-A-2)!\sum_{2\leq k\leq N-A}(A+k-3)!(k-1)/(k-2)!\)。
其中\(\sum_{0\leq k\leq B} {A+k\choose k}\)是一个经典问题。
他的封闭形式如下：
可以这样理解\(\sum_{k\leq B} {A+k\choose A}\)为组合数矩阵的\(A\)到\(A+B\)行的第\(A\)列的和。
由于\((x,y)+(x+1,y)=(x+1,y+1)\)。
所以最终恰好就是上面的值。