题解：CF1427F Boring Card Game

SegTree · 2025-10-24 11:29:40 · 题解

不考虑轮流，做法显然：

维护栈，每次往栈里插数，如果顶部 3 个颜色相同就将它们弹出，那么按照出栈序输出即可。

现在考虑轮流，发现能取相当于里面的东西都取干净了，类似于括号树的结构。于是建出括号树，问题转化为：

• 你需要构造轮流删除黑点和白点的方案，使得每个点删除时子树已经被删空。

删除黑点时，我们一定可以随意找到一个叶子删除。

证明：假设不存在黑叶子，那么所有叶子都是白的，考虑将每个黑点都任意匹配儿子中的一个白点，又因为方案存在，所以存在一个白点为根，因此有一个白点不被匹配，推知黑点个数小于白点个数。矛盾。

删除白点时，我们也可以用类似的方法证明，但是如果我们找到的点是根，下一步可能没有白根，因此，在存在不是白根的白叶子时，我们优先选择这样的点；否则选择白根。

时间复杂度视实现可 O(n) 至 O(n^2) 不等。

https://codeforces.com/contest/1427/submission/345435748。