2023HNUPC A

大意

给 一 个 长 度 为 n的 ， 只 包 含 A、 B、 C三 种 字 符 的 字 符 串 S。 问 S 中 包 含 多 少 个 三 元 组 (i,j,k)满 足 i<j<k并 且 \(S_iS_jS_k=ABC\) 或 \(CBA\) ， 且 每 一 个 字 符 最 多 使 用 一 次 。\((1\leq n \leq 3*10^5)\)

题解

把所有的A和C交换位置，使得所有A都在C之前，然后只需要计算三元组ABC的个数即可。（转化法）

证明正确性：

设交换后的为T，交换前为S。

尝试反过来想，我现在在T中选了很多ABC，现在要把其中的一些AC（不一定相邻）交换位置。那如果有两个"ABC"收到影响。一个变成了CBC，一个变成了ABA，假设CBC的B在ABA的B前面（反之同理），讨论A，C对于两个B的相对位置（其实只有4种情况）。

启发

这种很自由的题目，要多假设并用”反之同理“。自由的题目可转化成不自由的题目，如”ABC“”CBA“ => "ABC"。

2023HNUPC B

大意

题目中说，可以选择一些有相同颜色的元素，把他们的颜色改成单调不减，使得若干次操作后，所有数 组都单调不减。

题解

可以发现每次操作，等价于删除了一种颜色，若干次操作使得剩下的元素是单调不减的。

问题就变成求一个魔改的最长上升子序列，在相同颜色的元素出现位置首次位置保存一下当前的答案， 尾的位置更新一下当前的答案即可。用树状数组，线段树，或者上升子序列的二分算法都可实现。

（对于一组相同元素a，最后一定是连着的，所以它们只能接第一个a前面的元素，只能最后一个a后面的元素接它们）

启示

简化思想

联想模型

D

\(0!=1\)

一个很复杂的式子可能最后很简单。

E

博弈论

题意

给定n堆石子，第i堆石子有\(a_i\)个，每次操作可以从最左边 的石子堆中移除任意个石子(至少1个)，无法操作的人输。 两个人玩游戏。每人连续操作1次，问谁能胜利。 一共有T个case。

题解

如果最左边石子堆数量为1，则操作唯一，交换先后手。 如果最左边石子堆数量大于1，则当前操作的人必胜（若\(a_{i+1}>1\) 则取 \(a_i-1\)，让对手取最后的1；若 \(a_{i+1}=1\) 则取 \(a_i\) 个，让对手取 \(a_{i+1}\) 的1）。 如果当前没有石子，则当前操作的人必败。

如果每人每次连续操作k次。定义f(i,j)表示如果第i堆只剩j个石子，并且其左侧的石子全部拿完的状态下，先手是否能获胜状态。1表示先手必胜，0表示后手必胜。能证明若f(i,j)=1,则任意t<j,f(i,t)=1。

启示

让对手的操作唯一，让自己的状态能由自己控制

证明状态单调来减少状态数。