【CF1427F】Boring Card Game 解题报告
Terminus_Est
·
·
题解
【CF1427F】Boring Card Game 解题报告
题意
#### Solution
首先我们考虑一种弱化版的问题，即不考虑两个人轮流操作，构造一种方案满足题目条件。
设被第一个人拿走的卡牌的颜色是 $1$，被第二个人拿走的卡牌的颜色是 $0$，不难想到一个贪心的做法：将未被匹配的卡牌放入栈中，如果栈顶出现三个连续的颜色相同的卡牌就弹出栈。按照出栈的逆序进行操作。这样就可以得到一个不考虑顺序的构造方案。因为原题必然有解，所以一定有这样一个方案。
我们再考虑把每组被拿走的卡牌的左端和右端的卡牌想象成左括号和右括号，这样我们的过程可以被看成一个括号匹配。我们像如下结构建树：
这样，原先的卡牌们就变成了一个森林。
同时，我们给每个点赋一个颜色 $0$ 或 $1$ 代表它是先手取走的/后手取走的。不难发现，树上的父子之间颜色都是相反的。并且，我们发现，每个点代表的三张牌如果要被取走，当且仅当它的后代都被取走了。于是我们考虑构造一个操作序列使得满足先手、后手这样的序列，并证明这样的序列一定存在。
1、当先手取的时候，颜色 $0$ 和颜色 $1$ 的数量相同。假设当前没有颜色 $0$ 作为叶子，那么因为父子之间必然不同，所以我们考虑将每个颜色 $0$ 都和它的一个儿子匹配，这样显然没有颜色 $1$ 会作为任何一棵树的根。但是，因为原题有解，所以最后被取走的一定是颜色为 $1$ 的节点，也就是一定有颜色为 $1$ 的节点作为根，矛盾。所以这一步我们任意找一个颜色 $0$ 的叶子节点就可以了。
2、当后手取的时候，颜色 $1$ 的数量比颜色 $0$ 的数量多 1 。分两种情况考虑：颜色为 $1$ 的根只有 1 个/多个。
有多个根：假设没有颜色为 $1$ 的叶子，那么每个 $1$ 和 $0$ 进行匹配，因为 $0$ 少一个，不够玩，矛盾，所以必有一个颜色为 $1$ 的叶子。而且，取走当前叶子并不影响最后至少有一个 $1$ 根的性质，所以随便取即可。
只有一个根：如果这个根有儿子，那么这个根是取不走的，于是同上一种情况取即可；如果没有儿子而且只剩它本身，那么就取它就好了；否则必然有别的根为 $0$ 的树，这个时候的情况和先手取的情况类似。我们这个时候只要取非根的 $1$ 即可。
至此，全部构造完成。