CSP-J 2026 纸牌游戏 题解

· · 题解

好题啊！！

题目大意

给定一叠共 n 张的牌，从上到下的点数依次为 a_1,a_2,\ldots,a_n。共 m 种点数，每种点数 1,2,\ldots,m 都至少出现一次。每局游戏开始时桌面为空，打出一张点数为 k 的牌时：

现在进行 n 局相互独立的游戏，第 i 局依次打出第 i 张至第 n 张牌。对于每种点数，求有多少局游戏结束时，桌面上留有该点数的牌。

数据范围：2\le n \le 5\cdot 10^5，1\le m\le 3\cdot 10^5。

算法一

根据题意暴力模拟，每局游戏中每次打出一张牌，都使用 \mathcal{O}(n) 的方法遍历并修改桌面上的牌，总时间复杂度 \mathcal{O}(n^3)，可以通过测试点 1\sim 6，期望得分 24。

算法二

同算法一暴力模拟，但每局游戏时使用栈维护桌面上从左到右的点数序列，并用数组记录每种点数是否在栈中。每张打出的牌至多入栈和出栈各一次，因此一局游戏模拟所需复杂度为 \mathcal{O}(n)，总时间复杂度 \mathcal{O}(n^2)，可以通过测试点 1\sim 12，期望得分 48。

算法三

当序列 a 单调不减时，相同点数的牌连续出现，只会替换桌面上最右端的同点数牌，不会收走其他点数的牌。因此，第 i 局游戏结束时桌面上的点数序列，即序列 a_i,a_{i+1},\ldots,a_n 去重后的结果。

设 \mathrm{last}_x 为点数 x 最后一次在序列中出现的位置，则第 i 局游戏结束时留有点数 x 的牌，当且仅当 i\le \mathrm{last}_x，因此点数 x 对应的答案即为 \mathrm{last}_x。

此算法可以通过所有特殊性质 A 测试点，即测试点 7\sim 9 和 20，期望得分 16，结合算法二可以获得 52 分。

算法四

当 m=2 时，设最后一张牌的点数为 x，另一种点数为 y。点数 x 的牌会在所有局游戏结束时留在桌面上，其答案为 n。

如果第一张打出的牌的点数为 y，那么桌面最左侧始终留有点数为 y 的牌，最后桌面上的点数序列为 [y,x]；否则，最左侧的点数始终为 x，打出最后一张牌后，桌面上只剩点数为 x 的牌。因此，点数 y 对应的答案就是它在序列中的出现次数，直接统计即可。

此算法可以通过测试点 1\sim 3 与 13, 14，期望得分 20，结合算法二、三可以获得 60 分。

算法五

观察 m=2 的情形并推广，我们发现如下性质：如果 a_i=a_j，那么第 i 局与第 j 局游戏结束时，桌面上的点数序列相同。

不妨设 i<j。第 i 局游戏中，桌面上最左侧牌的点数始终为 a_i，尽管这张牌本身可能被后来打出的同点数牌替换。当打出第 j 张牌时，由于 a_j=a_i，桌面上原有的牌会被全部收走，再放上新打出的牌，此时只剩一张点数为 a_j 的牌。这与第 j 局游戏打出第一张牌后的状态相同，此后两局打出的牌也完全相同，因此最终点数序列相同。

也就是说，对于每种点数，以其作为第一张牌点数的所有游戏结果完全相同。我们只需为每种点数选一局游戏进行模拟，例如选择从其最后一次出现的位置开始的那一局。设点数 x 在原序列中出现了 \mathrm{cnt}_x 次，则模拟从 x 开始的游戏后，给最终留下的每种点数的答案加上 \mathrm{cnt}_x。一共只需模拟 m 局游戏，可以得到一个 \mathcal{O}(nm) 的算法。

该算法视实现可以通过前 17 个测试点到前 19 个测试点，期望得分 68\sim76。结合算法三可以获得 72\sim 84 分。

算法六

基于算法五的结论，假设 a_i 是该点数在序列中的最后一次出现，且 i<n，我们继续观察第 i 局与第 (i+1) 局游戏之间的关系。由于后续不会再打出点数为 a_i 的牌，这张牌始终留在最左侧，右侧的操作与第 (i+1) 局完全相同。因此，第 i 局游戏的最终点数序列，即为第 (i+1) 局游戏的最终点数序列前面插入一个 a_i 的结果。

现在考虑建立 m 个节点，编号依次为 1,2,\ldots,m，每个节点对应一种点数。对于每种点数 x，设 p=\mathrm{last}_x；若 p<n，则令节点 x 的父亲为 a_{p+1}。点数 a_n 对应的节点没有父亲，作为根。

由于 \mathrm{last}_{a_{p+1}}\ge p+1>\mathrm{last}_x，沿父亲方向，点数最后一次出现的位置严格递增，因此不会形成环，最终一定到达根 a_n，这些边构成一棵树。

由上述结论，以点数 x 开始的游戏，其最终点数序列就是从节点 x 开始一直向上到根的路径。因此，点数 x 会在以其子树内任意节点对应的点数开始的游戏中留下。

将节点 x 的权值赋为点数 x 在序列中的出现次数 \mathrm{cnt}_x，则其子树内所有节点的权值和就是答案。用一次遍历统计即可。

该算法的时间复杂度为 \mathcal{O}(n+m)，可以通过所有测试点，期望得分 100 分。