CSP-J 2026 入门组第四题：《纸牌游戏（card）》
这道题很有意思！它表面上是在玩纸牌，实际上考查的是 栈的思想、逆向思考，以及如何把重复的操作优化成线性时间。
前三题我们接触了字符串、位运算和贪心算法。第四题则要带大家认识一种新的思考方式：
当正着做很多遍太慢时，能不能倒过来做一次？
我们今天就跟着小 Z 一起玩一场纸牌魔法游戏！
一、先读懂游戏规则
想象小 Z 面前有一张长桌子，桌面上的纸牌从左向右排成一行。
每张牌上有一个点数，例如：
1、2、3、4
每次打出一张新牌时，有两种情况：
如果桌面上没有这种点数，就把新牌放到最右边。
如果桌面上已经有这种点数，就把它以及它右边的所有牌全部收走，再把新牌放到最右边。
注意：被收走的牌，本局游戏中就不能再使用了。
举个例子
桌面原来有：
接下来又打出一张点数为 4 的牌。
桌面原来是：
1 4 2 3
因为已经有一张 4，所以要把 4 以及它右边的 2、3 全部收走，再放入新的 4。
这就是游戏的基本规则。
二、题目到底让我们求什么？
题目给出 n 张牌，点数依次为：
a1, a2, ..., an
小 Z 要进行 n 局游戏。
第 1 局：打出第 1 张到第 n 张。
第 2 局：跳过第 1 张，打出第 2 张到第 n 张。
第 3 局：跳过前 2 张，打出第 3 张到第 n 张。
……
第 n 局：只打出最后一张。
也就是说，我们要分别处理这些后缀：
最后要统计：
有多少局结束时桌面上有点数 1？
有多少局结束时桌面上有点数 2？
有多少局结束时桌面上有点数 3？
注意：统计的是有多少局包含这种点数，不是这种点数的牌一共出现了多少次。
三、先用样例玩一遍
题目样例 1：
4 3 1 2 1 3意思是：
一共有 4 张牌；
点数种类有 3 种；
牌的顺序是
1 2 1 3。
我们先不考虑优化，看看每一局最后会怎样。
第 1 局：打出 1、2、1、3
操作 | 桌面 |
|---|---|
打出 1 | 1 |
打出 2 | 1 2 |
再打出 1 | 1 |
打出 3 | 1 3 |
最后是1 3。
第 2 局：打出 2、1、3
操作 | 桌面 |
|---|---|
打出 2 | 2 |
打出 1 | 2 1 |
打出 3 | 2 1 3 |
最后是2 1 3。
第 3 局：打出 1、3
最后是1 3。
第 4 局：只打出 3
最后是3。
因此：
点数 | 出现在最终桌面的局数 |
|---|---|
1 | 3 |
2 | 1 |
3 | 4 |
答案是：
3 1 4到这里，孩子应该已经理解题意了。
但问题来了：如果我们真的把每一局都模拟一遍，会不会太慢？
四、为什么不能直接模拟 n 局？
题目给出的数据范围是：
2 ≤ n ≤ 5 × 10^5，1 ≤ m ≤ 3 × 10^5；
最多有 50 万张牌，也就有 50 万局游戏。
如果每一局都重新模拟，最坏情况下可能要处理：
n+(n-1)+(n-2)+.......+1
这相当于：
当 n 达到 50 万时，这个操作量非常大，计算机很难在规定时间内完成。
所以，我们要想办法：
不要玩 50 万遍游戏，而是想办法只从头到尾处理一次牌。
这就是本题最重要的突破口。
五、真正的突破：从第一张牌开始，找到它最后一次出现的位置
现在我们换一种思考方式。
假设一局游戏的第一张牌是点数 1。
在这张 1 后面，可能出现很多其他点数。但是在最后一次出现 1 之前，桌面上的 1 始终不会被其他点数收走，因为其他点数只能收走自己以及右边的牌，不能收走左边的 1。
当 1 最后一次出现时，它会把自己右边的所有牌收走。
所以，在最后一次出现 1 之后，桌面一定可以看成：
1 + 后面剩余牌形成的最终桌面
这就是本题的关键！
1. 用样例理解这个规律
牌的顺序：
1 2 1 3
我们先看第一张牌 1。
所以，第 1 局最终桌面一定是：
1 + 第 4 张牌之后形成的桌面
第 4 张牌是 3，而且它后面没有牌了。
因此最终桌面是：
1 3
我们再看第 2 局：
2 1 3
第一张牌是 2，它最后一次出现的位置就是第 2 张牌。
因此：
2 + 第 3 张牌之后形成的桌面
第 3 张牌是 1，最后一次出现的位置就是第 3 张。
再接着看第 4 张牌 3。
最终桌面：
2 1 3
是不是很神奇？
我们不需要模拟每一张牌怎么被收走，只需要不断找到当前点数最后一次出现的位置！
2. 把这个规律变成算法
我们定义一个数组：
last[x]
表示点数 x 在整叠牌中最后一次出现的位置。
例如：
位置： 1 2 3 4 点数： 1 2 1 3那么：
点数 x | last[x] |
|---|---|
1 | 3 |
2 | 2 |
3 | 4 |
接下来定义：
nxt[i] = last[a[i]] + 1;它表示：
如果从第 i 张牌开始玩，第一张牌的最后一次出现位置之后，下一次应该从哪里继续寻找。
对于样例：
a: 1 2 1 3 位置: 1 2 3 4得到：
起点 i | a[i] | last[a[i]] | nxt[i] |
|---|---|---|---|
1 | 1 | 3 | 4 |
2 | 2 | 2 | 3 |
3 | 1 | 3 | 4 |
4 | 3 | 4 | 5 |
这里的 5 表示已经超过最后一张牌，游戏结束。
于是，我们得到几条路线：
这条路线上的每个数字，就是最终桌面上留下的点数。
六、第二个关键：一条路线可能被很多局共同使用
现在我们已经知道了每一局最终桌面上的数字是怎样找到的。
但还有一个问题：
题目要求统计每个点数出现在多少局中。
如果每一局都沿着路线走一遍，仍然可能很慢。
所以我们再想一步：
如果很多局都会经过同一个位置，能不能把它们合并统计？
答案是可以的。
我们定义：
ways[i]
表示有多少局游戏的寻找路线会经过第 i 个位置。
举个例子：
位置： 1 2 3 4 点数： 1 2 1 3前面我们算出了：
nxt[1] = 4 nxt[2] = 3 nxt[3] = 4 nxt[4] = 5每一局都从自己的起点开始，所以每个位置最初都有 1 条路线经过它。
因此：
ways[i] = 1;但是路线还会继续向后走。
例如：
第 1 个位置的路线会走到第 4 个位置；
第 2 个位置的路线会走到第 3 个位置；
第 3 个位置的路线也会走到第 4 个位置。
我们把这些路线数量累加起来。
1. 路线数量如何传递？
核心代码只有两行：
ways[nxt[i]] += ways[i];意思是：
第 i 个位置有多少条路线经过，就把这些路线全部传递给它的下一个位置。
我们从左到右处理，因为nxt[i]一定大于 i。
2. 手工推演 ways 数组
初始：
位置： 1 2 3 4 ways： 1 1 1 1处理第 1 个位置：
nxt[1] = 4
把第 1 个位置的 1 条路线传给第 4 个位置：
ways：1 1 1 2处理第 2 个位置：
nxt[2] = 3
把第 2 个位置的 1 条路线传给第 3 个位置：
ways：1 1 2 2处理第 3 个位置：
nxt[3] = 4
第 3 个位置现在有 2 条路线经过，所以把 2 加到第 4 个位置：
ways：1 1 2 4处理第 4 个位置：
它的下一位置是 5，已经超出范围，不需要再传递。
最终得到：
位置 | 点数 | ways[i] |
|---|---|---|
1 | 1 | 1 |
2 | 2 | 1 |
3 | 1 | 2 |
4 | 3 | 4 |
这意味着：
第 1 个位置有 1 局会经过；
第 2 个位置有 1 局会经过；
第 3 个位置有 2 局会经过；
第 4 个位置有 4 局会经过。
七、最后一步：统计每种点数出现的局数
现在就非常简单了！
每个位置上的点数是a[i]，而ways[i]表示有多少局会经过这个位置。
因此：
ans[a[i]] += ways[i];把经过这个位置的路线数量，累加到对应点数的答案中。
对于样例：
位置 | 点数 | ways[i] | 累加到 |
|---|---|---|---|
1 | 1 | 1 | ans[1] += 1 |
2 | 2 | 1 | ans[2] += 1 |
3 | 1 | 2 | ans[1] += 2 |
4 | 3 | 4 | ans[3] += 4 |
最终：
ans[1] = 3 ans[2] = 1 ans[3] = 4输出：
3 1 4样例答案正确
这里有一个重要细节：为什么可以直接把ways[i]加到ans[a[i]]？
因为一条路线不会经过同一种点数的两个位置。
当路线经过点数 x 的位置 i 时，它的下一位置是last[x]+1，已经跳过了 x 在后面所有出现的位置。因此，每一局的路线中，每种点数最多出现一次，不会重复计数。
八、完整 C++ 参考程序
现在把前面学到的内容组合起来。
#include <iostream> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; vector<int> a(n + 1); vector<int> last(m + 1, 0); vector<int> nxt(n + 1); vector<long long> ways(n + 1, 1); vector<long long> ans(m + 1, 0); // 第一步：读入牌，并记录每种点数最后出现的位置 for (int i = 1; i <= n; i++) { cin >> a[i]; last[a[i]] = i; } // 第二步：计算每个位置的下一个位置 for (int i = 1; i <= n; i++) { nxt[i] = last[a[i]] + 1; } // 第三步：从左到右传递路线数量 for (int i = 1; i <= n; i++) { if (nxt[i] <= n) { ways[nxt[i]] += ways[i]; } } // 第四步：统计每种点数出现的局数 for (int i = 1; i <= n; i++) { ans[a[i]] += ways[i]; } // 第五步：输出答案 for (int i = 1; i <= m; i++) { cout << ans[i]; if (i < m) cout << " "; } cout << endl; return 0; }九、把整个算法整理成五个步骤
我建议记住下面这张流程图：
第一步：记录最后出现位置
last[x] = 点数 x 最后出现的位置
第二步：计算下一个位置
nxt[i] = last[a[i]] + 1
第三步：传递路线数量
ways[nxt[i]] += ways[i]
第四步：统计每种点数
ans[a[i]] += ways[i]
第五步：输出答案
十、复杂度分析：为什么它能通过考试？
我们看看程序做了多少工作。
操作 | 时间复杂度 |
|---|---|
读入数据，记录 last | O(n) |
计算 nxt | O(n) |
传递 ways | O(n) |
统计答案 | O(n) |
输出答案 | O(m) |
总时间复杂度：
O(n+m)
空间复杂度：
O(n+m)
题目最大 n 为 50 万，m 为 30 万，这样的算法是可以高效处理的。
十一、最容易犯的四个错误
错误 1：把每一局都重新模拟一遍。
这样最坏需要 O(n^2) 的时间，会超时。
错误 2：把last[a[i]]当作下一个位置。
不对！我们要跳过最后一次出现的位置，所以必须加 1：
nxt[i] = last[a[i]] + 1;错误 3：从右向左传递 ways。
本题的下一个位置一定大于当前位置，因此要从左向右传递：
for (int i = 1; i <= n; i++)错误 4：只统计每个位置一次。
ways[i]不是固定的 1，它代表有多少局会经过这个位置。必须使用：
ans[a[i]] += ways[i];而不是简单地ans[a[i]]++。
十二、举一反三：让孩子真正掌握这道题
这道题真正值得学习的，不只是纸牌游戏，而是三个算法思想。
最后一次出现位置：遇到重复元素时，思考它最后一次出现的位置有什么作用。
跳跃式处理：不必一个位置一个位置地走，可以直接跳到关键位置的后面。
路线数量合并：很多起点会走到同一个位置，可以把经过这个位置的路线数量累加起来。
给孩子留两道小练习。
练习 1：魔法数字牌
输入：
5 3 1 2 3 2 1请完成：
求出
last[1]、last[2]、last[3]。求出每个位置的
nxt[i]。计算
ways[i]。最后求出三个点数的答案。
练习 2：自己设计一个小纸牌游戏
输入：
6 3 1 2 1 3 2 3请尝试使用程序求解，并且用纸笔验证其中第 1 局和第 3 局的最终桌面。
这道题看起来是在考纸牌模拟，其实它考的是学生能不能从一大堆重复操作中，找到真正有用的信息。
先找到每种点数最后出现的位置，再建立位置之间的跳跃关系，最后把经过每个位置的路线数量合并起来。
这是一种很值得培养的算法思维：
不要重复做相同的事情，而要找到可以共享的计算结果。
