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注意统计的是有多少局包含这种点数不是这种点数的牌一共出现了多少次。三、先用样例玩一遍题目样例 14 3 1 2 1 3意思是一共有 4 张牌点数种类有 3 种牌的顺序是1 2 1 3。我们先不考虑优化看看每一局最后会怎样。第 1 局打出 1、2、1、3操作桌面打出 11打出 21 2再打出 11打出 31 3最后是1 3。第 2 局打出 2、1、3操作桌面打出 22打出 12 1打出 32 1 3最后是2 1 3。第 3 局打出 1、3最后是1 3。第 4 局只打出 3最后是3。因此点数出现在最终桌面的局数132134答案是3 1 4到这里孩子应该已经理解题意了。但问题来了如果我们真的把每一局都模拟一遍会不会太慢四、为什么不能直接模拟 n 局题目给出的数据范围是2 ≤ n ≤ 5 × 10^51 ≤ 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那么点数 xlast[x]132234接下来定义nxt[i] last[a[i]] 1;它表示如果从第 i 张牌开始玩第一张牌的最后一次出现位置之后下一次应该从哪里继续寻找。对于样例a: 1 2 1 3 位置: 1 2 3 4得到起点 ia[i]last[a[i]]nxt[i]1134222331344345这里的 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 个位置ways1 1 1 2处理第 2 个位置nxt[2] 3把第 2 个位置的 1 条路线传给第 3 个位置ways1 1 2 2处理第 3 个位置nxt[3] 4第 3 个位置现在有 2 条路线经过所以把 2 加到第 4 个位置ways1 1 2 4处理第 4 个位置它的下一位置是 5已经超出范围不需要再传递。最终得到位置点数ways[i]111221312434这意味着第 1 个位置有 1 局会经过第 2 个位置有 1 局会经过第 3 个位置有 2 局会经过第 4 个位置有 4 局会经过。七、最后一步统计每种点数出现的局数现在就非常简单了每个位置上的点数是a[i]而ways[i]表示有多少局会经过这个位置。因此ans[a[i]] ways[i];把经过这个位置的路线数量累加到对应点数的答案中。对于样例位置点数ways[i]累加到111ans[1] 1221ans[2] 1312ans[1] 2434ans[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; vectorint a(n 1); vectorint last(m 1, 0); vectorint nxt(n 1); vectorlong long ways(n 1, 1); vectorlong 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]第五步输出答案十、复杂度分析为什么它能通过考试我们看看程序做了多少工作。操作时间复杂度读入数据记录 lastO(n)计算 nxtO(n)传递 waysO(n)统计答案O(n)输出答案O(m)总时间复杂度O(nm)空间复杂度O(nm)题目最大 n 为 50 万m 为 30 万这样的算法是可以高效处理的。十一、最容易犯的四个错误错误 1把每一局都重新模拟一遍。这样最坏需要 O(n^2) 的时间会超时。错误 2把last[a[i]]当作下一个位置。不对我们要跳过最后一次出现的位置所以必须加 1nxt[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 局的最终桌面。这道题看起来是在考纸牌模拟其实它考的是学生能不能从一大堆重复操作中找到真正有用的信息。先找到每种点数最后出现的位置再建立位置之间的跳跃关系最后把经过每个位置的路线数量合并起来。这是一种很值得培养的算法思维不要重复做相同的事情而要找到可以共享的计算结果。