AGC做题记录

从比较远古的题开始做起吧。

AGC001

C

经典题。

考虑直径中点，讨论长度奇偶性直接\(O(n^2)\)做就行。

提交记录

D

不是很难的构造题。

思考题目给出的条件，不难想到把等价关系转化为连边，那么序列合法等价于形成了一个连通块。

这时候考虑连通块的一些必要条件，就是边数大于等于\(n - 1\)，可以推导出\(A\)中奇数不超过2个。这时需要大胆猜想这是有解的充要条件，直接构造答案。

我在做题时到这一步就没思路了，其实可以考虑一些比较弱的情况，每次只连出来一个点，也就是\(B\)刚好是\(A\)右移一位，不难发现这个构造是对的。考虑奇数怎么做，其实直接把奇数丢到首尾就行了因为这个时候两端不会连到另一个\(B\)的回文串内。

提交记录

E

典中典之组合意义。

很容易把这个东西变成\((0,0)\rightarrow(a_i+b_i+a_j+b_j) \iff (-a_i,-b_i) \rightarrow (a_j,b_j)\)的方案数，那么dp算就行了。

提交记录

F

非常有意思的思维题。

第一步就把我难住了，这个交换的条件显然非常散乱，难以找寻到其中的性质。题解给出了一种巧妙的思维方式：考虑将排列\(P\)视为置换，这个置换的逆。假设这个逆置换为\(Q\)，那么\(P\)字典序最小等价于\(Q\)字典序最小，而我们可以对\(Q\)进行的操作就是当相邻两个数之差的绝对值大于等于\(K\)时，可以交换它们。

这个转化是大胆的，但它毫无疑问极大地简化了问题。

这个时候不难想到直接对\(Q\)进行冒泡排序，因为不能交换的数的相对顺序确定，所以这个贪心排序是正确的。我们就得到了一个\(O(n^2)\)的做法

既然想到了冒泡排序，那么不妨试着优化，对于和“排序”有关的一类题目，都可以考虑进行归并。

容易发现，右区间的\(j\)优于左区间的\(i\)当且仅当左区间中\(i\)的后缀最小值不小于\(Q_j+K\)。这个后缀最小值可以直接维护。复杂度\(O(n\log n)\)

相较于线段树优化拓扑排序，我认为这种思路比较自然也比较优秀。

提交记录