P8866 题解（未完） 最后更新于 2025-05-01 22:09:58

注：由于某些原因，阅读可能较为困难，请使用 Dark Reader 插件。 ### $\color{red}\texttt{Part 1: Description}$ 小 E 喜欢上了一款叫做《喵了个喵》的游戏。这个游戏有一个牌堆和 $n$ 个可以从栈底删除元素的栈，任务是要通过游戏规则将所有的卡牌消去。开始时牌堆中有 $m$ 张卡牌，从上到下的图案分别是 $a_1, a_2,\dots, a_m$。所有的卡牌一共有 $k$ 种图案，从 $1$ 到 $k$ 编号。牌堆中每一种图案的卡牌都有偶数张。开始时所有的栈都是空的。这个游戏有两种操作： - 选择一个栈，将牌堆顶上的卡牌放入栈的顶部。如果这么操作后，这个栈最上方的两张牌有相同的图案，则会自动将这两张牌消去。 - 选择两个不同的栈，如果这两个栈栈**底**的卡牌有相同的图案，则可以将这两张牌消去，原来在栈底上方的卡牌会成为新的栈底。如果不同，则什么也不会做。 这个游戏一共有 $T$ 关，小 E 一直无法通关。请你帮小 E 设计一下游戏方案，即对于游戏的每一关，给出相应的操作序列使得小 E 可以把所有的卡牌消去。 --- ### $\color{orange}\texttt{Part 2: Solution, For a partial subproblem solution with k = 2n - 2}$ 该部分分难度级别：$\color{yellow}\texttt{35/100}$ 考虑对于每一个满足 $1\le i<n$ 的栈 $i$，将 $2\times i-1$ 和 $2\times i$ 两个种类的图案放入这个栈中。 于是编号为 $n$ 的栈没有分配到任何的元素，作为一个“备用栈”使用。 然后将 $m$ 个卡牌依次放入栈中。 设当前插入的卡牌应该插入 $p$ 号栈中（$1\le p<n$）。 分类讨论： + 如果 $p$ 号栈为空，那么将当前应该插入的卡牌插入 $p$ 号栈中。执行了 $1$ 次操作。 + 如果 $p$ 号栈中有且仅有一个卡牌，那么： + 如果 $p$ 号栈的卡牌的花色和当前要插入的卡牌的花色相同，那么将当前应该插入的卡牌插入 $p$ 号栈中，这样会自动地将两个卡牌消除。执行了 $1$ 次操作。 + 如果 $p$ 号栈的卡牌的花色和当前要插入的卡牌的花色不同，那么将当前应该插入的卡牌插入 $p$ 号栈中。执行了 $1$ 次操作。 + 如果 $p$ 号栈中有且仅有两个卡牌，那么： + 如果 $p$ 号栈的卡牌的花色和当前要插入的卡牌的花色相同，那么将当前应该插入的卡牌插入 $p$ 号栈中，这样会自动地将两个卡牌消除。执行了 $1$ 次操作，此时该栈中剩余 $1$ 个卡牌。 + 如果 $p$ 号栈的卡牌的花色和当前要插入的卡牌的花色不同，那么由于当栈 $p$ 中存在两个卡牌的时候，两个卡牌必然一个位于栈顶一个位于栈底，且两个卡牌的花色不相同。于是将当前的卡牌插入到备用栈 $n$ 号栈中，然后选中栈 $p$ 和 栈 $n$ 并执行一次 $2$ 号操作，将这两个栈的栈底元素消除即可。执行操作完毕之后，栈 $n$ 中没有元素，栈 $p$ 中剩余 $1$ 个元素，执行了 $2$ 次操作。 显然满足 $m\le op\le 2\times m$ 的限制条件。 时间复杂度 $O(n)$，可以通过 $T=1001$ 的部分分。 ### $\color{yellow}\texttt{Part 3: Solution, For a partial subproblem solution with k = 2n - 1}$ 该部分分难度级别：$\color{orange}\texttt{64/100}$ ### $\color{green}\texttt{Part 4: Code}$ 咕。 $\color{gray}\tiny{\text{本文作者}}\color{gray}\texttt{luogu uid=378467}\text{转载请附上此段声明，谢谢QwQ}$