估计不到10题就弃坑了

AGC054B

如果最后 Takahashi 取走的橘子的下标依次是 \(a_1,a_2...a_k\)，Aoki 是 \(b_1,b_2...b_{n-k}\)，那么如果 \(a,b\) 确定，\(p\) 也就唯一确定了。

数 \(a,b\) 很简单。考虑这个结论的正确性：

首先第一个该 Takahashi 选，所以 \(p_1=a_1\)。

之后如果该 Takahashi 选就让 \(p=a\)，否则就让 \(p=b\)。

由于双方取的橘子质量都是 \(\sum w/div 2\) ，所以也不可能出现该某个人选但这个人已经选完了的情况（如果选完了那么接下来全部橘子显然都该另一个人选了）。

AGC054C

考虑对于 \(P\) 如何求出最小交换次数。令 \(P_{pos_i}=i\)。

容易想到一个贪心策略：依次考虑 \(1,2...n\)，如果当前 \(pos_i\) 前面比 \(i\) 大的数不超过 \(k\) 就不管，否则暴力往左边调整直到前面比 \(i\) 大的数不超过 \(k\)为止。

最优性：这个比较显然，因为我们每次选最小的一个数调整，如果先调整大的肯定不会更优。

正确性：这不更显然吗，显然后面调整的数不会把已经调好的数往右边挤，所以正确性显然。

然后我就开始各种数数，发现数 \(pos\) 数不出来，数其它的也数不出来，但就是没想到直接数 \(x_i\)（菜是原罪）。

设 \(x_i\) 表示排列 \(P\) 在 \([1,pos_i)\) 内比 \(i\) 大的数的个数，\(x^{\prime}_i\) 表示 \(P^{\prime}\) 的。那么有 \(x^{\prime}_i=\min(x_i,k)\)。

\(x^{\prime}\) 是可以直接求的。如果 \(x^{\prime}_i<k\)，显然 \(x_i\) 唯一确定。否则，\(k\le x_i\le n-i\)。

显然可以归纳法证明每个 \(x\) 唯一对应一个排列 \(P\)显然确实显然但我就是注意不到。于是答案即为 \(\prod\limits_{cnt_i=k}(n-i-k+1)\)。

这种数排列的题 agc 貌似还挺喜欢出的，agc056b 也是。基本上这种题目都需要先分析一堆性质和结论，然后找到一个对应且唯一对应一个排列的东西，并且要求这个东西是好数的，最后把这个东西数出来就好了。