以思维方式为主。

简单题

AGC053C

关键词：概率期望，拆贡献，归纳证明

首先一定是把没有 \(2n\) 的那堆删光，设这堆为 \(A\)，另一堆为 \(B\)。考虑一种牌堆的最优方案。
先有一种简单的情况：当前所有的 \(A_i\) 都满足它的下面都有一个小于它的 \(B_j\)，此时存在策略，从上往下优先把 \(A_i<B_i\) 的给删掉，这样递归下去一定能在不删任何 \(B_i\) 的情况下删光 \(A\)。
如果出现了一个 \(A_i\) 满足 \(\forall j\leq i,A_i>B_j\)，那么考虑改进上面的过程，先去将最小的满足如上条件的 \(i\) 处不断删掉 \(B_i\) 使得 \(A_i<B_i\)，不断重复这个过程，然后按上面的过程做就行了。这样显然不会让原先下面有一个小于它的 \(B_j\) 的 \(i\) 的那个 \(B_j\) 无法找到。
于是设 \(d\) 表示所有 \(i\) 中第一个大于 \(A_i\) 的 \(B_j\) 的 \(j-i\) 的最大值，答案为 \(n+d\)。

中等题

难题