企业官网建设流程全解析

看到“交易账本”这个题名，很多从省赛冲上来的选手第一反应是拿哈希表模拟转账，写完提交才发现撤销操作直接让整个程序逻辑崩掉。2023年蓝桥杯国赛这道题，表面考的是一个账本，实际上考的是你对“操作撤销”这个模型的理解。题目起名接地气，内核却是一道非常典型的栈模拟题，无论你报的是Java组、C++组还是Python组，这道题的解题思路都是通用的。

这篇文章我会把这道题的题面先还原清楚，再从朴素做法一步步推导到正解，中间把“为什么撤销一定对应栈”这个关键点讲透，最后给出C++和Java两个完整可提交的版本，并附上我在现场调试时踩过的几个坑。不管你是准备下一届蓝桥杯，还是单纯想练一练数据结构题，这篇文章都值得看完。

1. 先从题面说起：交易账本到底考什么

1.1 还原题目描述

题目大意是这样的：初始时有若干个账户，所有账户余额为0。接下来有n条操作指令，操作分为两种类型。

第一种是交易指令，格式为1 x y z，表示账户x向账户y转账z元。这个操作会真实改变两个账户的余额，转出方余额减少z，转入方余额增加z。

第二种是撤销指令，格式为2 k，表示撤销最近k笔真实的交易。注意这里撤销的对象是“交易”，不是“指令”。也就是说，如果之前有若干笔交易已经被撤销了，那么它们就不再参与计数，不能被再次撤销。撤销操作本身不是交易，也不会被计入后续撤销的范围内。

所有操作执行完之后，需要按账户编号从小到大，输出每个账户的最终余额。

题目里还有一个容易被忽略的边界规则：如果当前尚未被撤销的交易总数不足k笔，那么直接撤销掉全部剩余交易。这个规则很重要，很多人在这里栽过跟头。

我举个例子。假设有下面这些操作：

6 1 1 2 10 1 2 3 5 2 1 1 3 1 3 2 2 1 2 1 100

逐步推演一下。

交易1：账户1向账户2转账10。此时余额为：1号账户-10，2号账户10，3号账户0。

交易2：账户2向账户3转账5。余额变为：1号-10，2号5，3号5。

撤销1：撤销最近1笔交易，也就是交易2。回滚后余额恢复为：1号-10，2号10，3号0。

交易3：账户3向账户1转账3。余额变为：1号-13，2号10，3号3。

撤销2：撤销最近2笔交易。现在尚未被撤销的交易是交易1和交易3，最近的顺序是先交易3、再交易1。回滚交易3时余额变为：1号-10，2号10，3号0；回滚交易1时余额变为：1号0，2号0，3号0。

交易4：账户2向账户1转账100。最终余额为：1号100，2号-100，3号0。按账户编号升序输出，结果就是：

1 100 2 -100 3 0

这个样例很有价值，因为它展示了撤销操作会把栈中“古老”的交易也弹出去。交易1是在交易2之前发生的，但交易2被撤销后，交易1仍然保留在栈中，直到最后被新一轮撤销波及。

1.2 考点定位与难度分析

这道题在当年的国赛题里属于“想到了就很简单，想不到就卡死”的类型，难度大概在中等偏易。它不涉及高深的算法，甚至连二分、排序都不需要，唯一的难点在于你能不能把“撤销最近k笔交易”这个描述转换成“从栈顶弹出k个元素”这个操作。

蓝桥杯近年来很喜欢出这种“披着业务场景外衣的数据结构题”。账本、队列、调度、日志这类名词看似陌生，剥掉外壳之后底层的模型往往非常简单。准备这类比赛的选手，最需要训练的能力就是把现实场景翻译成数据结构语言。

从命题角度看，这道题考察了两个基本功：一是对栈的先进后出特性是否真正理解，二是对“撤销”这个抽象操作的代码落地能力。很多选手能说出栈的特性，但一上手写撤销逻辑就乱了，原因在于没有把“回滚余额”和“弹出栈记录”这两个动作绑定在一起。

2. 从朴素做法到栈模拟的思维过程

2.1 朴素数组方案的致命缺陷

很多人的第一版代码是这样的：开一个数组记录每个账户的余额，再来一个数组从头到尾存所有交易记录，遇到撤销指令时，从数组末尾往前数k条，对余额做反向操作。

这个思路在数据小的时候完全没问题，但仔细一推就会发现它根本走不通。问题出在“被撤销的交易”和“仍然有效的交易”混在一起了。

假设当前交易数组中有5笔交易，其中第2笔已经被之前的撤销操作撤销掉了。此时又来一条撤销3的指令，它应该撤销哪3笔？按题意，应该是最近3笔“仍然有效”的交易。如果用普通数组顺序往前扫，你需要跳过那些已经失效的交易，这就涉及给交易打标记、维护“最近的一个有效交易位置”之类的工作。

更麻烦的是，如果后续又追加了新的交易，那么“偏移量”还会继续变化。每来一次撤销指令，你都需要从尾部往前寻找若干条有效交易，这个寻找过程在最坏情况下是O(n)的，整体复杂度会退化到O(n²)。在n达到几十万甚至上百万的赛事数据面前，这基本等于超时。

有人会想用链表来做，维护一个指向“最后一个有效交易”的指针，撤销时沿着prev指针往前跳k步。这个思路比数组好一些，但仍然要解决“哪些交易被跳过”的问题，代码复杂度陡增。而且每次回滚余额后，如果还要删除节点，链表的指针维护也容易出错。

2.2 为什么撤销操作天然对应栈

我们先停下来想一个问题：一个交易被撤销后，什么情况下它会对后续操作产生影响？答案是不会。一笔交易一旦被撤销，它的余额影响就被完全抹除，未来也不再参与任何撤销计数。它就像从来没有发生过一样。

那么，“当前仍然生效的交易集合”是怎么变化的？

新来一笔交易，就向这个集合中加入一条记录；撤销k笔交易，就从集合尾部移除k条记录。注意，移除的永远是最新加入的记录，后加入的先被移除。这就是典型的“后进先出”，也就是栈。

栈的模型和这道题是完美匹配的。维护一个交易栈，栈底是最早发生的有效交易，栈顶是最近发生的有效交易。新交易来临时执行入栈操作，撤销来临时执行k次出栈操作。每一次入栈和出栈都同步修改账户余额，就得到了当前真实状态。

这里有一个很多人容易绕进去的点：为什么撤销操作本身不入栈？因为题目说的是撤销“交易”，交易才需要入栈。撤销指令只是从栈中弹出元素，它本身没有余额影响，也不需要被未来的撤销操作“撤销”。明确这一点之后，代码结构就非常清晰了。

2.3 正确性证明的关键点

可以把整个维护过程抽象成两个不变式。

第一个不变式：栈中从底到顶的所有交易，恰好是当前所有尚未被撤销的交易，并且顺序和发生顺序一致。每次交易指令相当于push，每次撤销指令相当于执行k次pop。只要保证push和pop的数量正确，这个不变式永远成立。

第二个不变式：当前所有账户的余额，等于从初始状态出发，按序执行栈中所有交易后的余额。既然栈中的交易是“所有尚未被撤销的交易”，那么只要在push时正向执行交易、在pop时反向执行交易，这个不变式就不会被破坏。

这两个不变式同时成立，最终算法就是正确的。我建议看这篇文章的同学，在赛场上或者练习时也养成这个习惯：写数据结构题之前，先在草稿纸上写下两个不变量，然后用它们去验证你的操作。这比盲目调试有效得多。

3. 算法细节与边界条件

3.1 数据结构与状态设计

正式实现时，栈中每个元素需要保存一笔交易的完整信息。最简单的方式是定义一个结构体，里面存储三个字段：转出账户from、转入账户to、转账金额val。

struct Transaction { int from, to; long long val; };

账户余额用哈希表维护。为什么不直接用数组？因为账户编号不一定连续，可能从1到1e9之间散落，稀疏的账户编号用数组会浪费大量空间，甚至直接越界。C++用unordered_map，Java用HashMap，Python用字典，都是标准做法。

有些人会问，能不能用并查集或者优先队列来做？并查集适合处理连通性和集合合并问题，优先队列适合处理带优先级的取出问题，它们都不适合维护“最近发生的若干个元素”这个顺序关系。栈是这个场景下逻辑最简单的答案，也是最不容易写错的选择。

3.2 细节处理：不足k笔时的规则、回滚顺序、自转账

先说不足k笔的情况。题目明确说如果剩余有效交易不足k笔，就全部撤销。代码写起来其实很简短：

while (k > 0 && !stk.empty()) { // 出栈并回滚 k--; }

这个写法同时处理了“k很大”和“栈为空”两种边界情况，不会有越界风险。如果你用for循环配合动态条件，反而容易写多出错。

再说回滚顺序。撤销最近k笔交易，回滚的顺序必须严格遵守从栈顶到栈底的方向。为什么？假设最近两笔交易是A、B，B在栈顶，A在栈底。撤销这两笔时，应该先回滚B，再回滚A。如果顺序反过来，虽然最终余额可能是对的，但中间状态会与历史真实状态不一致。在一个只有最终余额输出的题目里，中间状态不会影响结果，但这是一种非常危险的编程习惯，一旦后续题目要求每撤销一次输出一次余额，顺序错了就全盘皆输。

最后说自转账。如果一笔交易的x等于y，也就是账户给自己转账，余额实际上没有变化。但注意，这笔交易仍然是一笔真实发生的交易，后续撤销操作计数时必须把它算进去。代码实现上不需要特判，直接执行balance[x]减去z，再balance[y]加上z，如果x等于y，一减一加正好抵消。入栈和回滚也是对称的，不会产生错误。

3.3 复杂度与数据范围分析

每个交易指令最多被push一次、pop一次，因此所有操作的总额外开销是O(n)级别的。账户数量记为m，如果使用哈希表存余额，单次查询和修改的平均复杂度是O(1)；最终输出前需要对账户编号排序，排序复杂度是O(m log m)。

所以整个算法的时间复杂度是O(n + m log m)，空间复杂度是O(n + m)。这个复杂度在蓝桥杯的评测数据下非常充裕，即使n到10的6次方也完全能跑过。

关于金额的数据范围，这里必须强调一个高频坑：转账金额和账户余额都可能超过int范围。C++里一定要用long long，Java里用long。我在写题解和帮人看代码时，见过太多因为int溢出而AC变WA的案例，这是蓝桥杯最容易丢分的地方之一。

4. 完整代码实现（C++ / Java 双版本）

4.1 C++实现与逐段说明

#include <bits/stdc++.h> using namespace std; struct Transaction { int from, to; long long val; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<Transaction> stk; stk.reserve(n); unordered_map<int, long long> balance; for (int i = 0; i < n; i++) { int op; cin >> op; if (op == 1) { int x, y; long long z; cin >> x >> y >> z; stk.push_back({x, y, z}); balance[x] -= z; balance[y] += z; } else { int k; cin >> k; while (k > 0 && !stk.empty()) { Transaction cur = stk.back(); stk.pop_back(); balance[cur.from] += cur.val; balance[cur.to] -= cur.val; k--; } } } vector<int> ids; ids.reserve(balance.size()); for (auto& p : balance) { ids.push_back(p.first); } sort(ids.begin(), ids.end()); for (int id : ids) { cout << id << " " << balance[id] << "\n"; } return 0; }

代码的关键点有三个。

第一，stk.reserve(n)做了提前扩容，避免了vector在反复push_back过程中多次动态扩容带来的开销。虽然不写也能过，但这是竞赛选手应该有的优化意识。

第二，unordered_map的默认行为是访问一个不存在的key时会自动插入并初始化为0，所以balance[x] -= z不需要提前判断x是否存在。这个特性在本题是安全的。

第三，最终收集所有出现过账户的key，排序后输出。如果不排序，哈希表的遍历顺序是不确定的，提交后大概率会因为输出顺序错误而WA。

4.2 Java实现与注意事项

import java.util.*; public class Main { static class Transaction { int from, to; long val; Transaction(int from, int to, long val) { this.from = from; this.to = to; this.val = val; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Deque<Transaction> stack = new ArrayDeque<>(); Map<Integer, Long> balance = new HashMap<>(); for (int i = 0; i < n; i++) { int op = sc.nextInt(); if (op == 1) { int x = sc.nextInt(); int y = sc.nextInt(); long z = sc.nextLong(); stack.push(new Transaction(x, y, z)); balance.put(x, balance.getOrDefault(x, 0L) - z); balance.put(y, balance.getOrDefault(y, 0L) + z); } else { int k = sc.nextInt(); while (k > 0 && !stack.isEmpty()) { Transaction t = stack.pop(); balance.put(t.from, balance.getOrDefault(t.from, 0L) + t.val); balance.put(t.to, balance.getOrDefault(t.to, 0L) - t.val); k--; } } } List<Integer> ids = new ArrayList<>(balance.keySet()); Collections.sort(ids); StringBuilder sb = new StringBuilder(); for (int id : ids) { sb.append(id).append(' ').append(balance.get(id)).append('\n'); } System.out.print(sb); } }

Java版本有几个地方要特别说明。

Scanner在蓝桥杯的Java环境中能正常读取，但如果n达到10的6次方，Scanner的解析速度就不太够用了。建议数据量大的时候换成BufferedReader + StringTokenizer来写。我在这里为了代码可读性保留了Scanner，实际比赛时你可以自己封装一个FastScanner。

HashMap的get操作在key不存在时会返回null，所以写入余额时必须使用getOrDefault，否则会触发NullPointerException。这是Java选手第一次写这类题最常见的报错。

Deque的push和pop方法在Java中分别对应栈的压入和弹出，ArrayDeque是比Stack更好的选择，因为Stack的线程安全是多余的，性能反而受影响。

最后用StringBuilder拼接输出而不是多次调用System.out.println，在大数据量下能有明显的性能提升。

4.3 手跑样例验证

用前文那个样例来验证代码逻辑：

6 1 1 2 10 1 2 3 5 2 1 1 3 1 3 2 2 1 2 1 100

跑一遍C++代码，输出：

1 100 2 -100 3 0

和手推结果完全一致。

这里建议所有拿到代码的人，不要急着提交，先自己构造几组小数据，把push、pop、回滚这三个动作画在纸上走一遍。我给你一个非常好用的小数据的构造思路：先加三笔交易，再撤销2笔，然后加一笔交易，再撤销1笔，最后输出。这个序列几乎覆盖了所有关键分支：正常入栈、跨区间撤销、栈中残留古老交易、不足k笔的边界处理。

5. 踩坑记录与自查清单

5.1 我现场踩过的几个坑

第一个坑是回滚顺序写反。我的第一版代码在撤销时从栈底往前回滚，想着“把最近k笔交易全部还原”，结果遇到嵌套撤销时余额怎么都不对。后来意识到，回滚必须是严格从栈顶往下的逆序过程。栈顶代表最近发生的交易，撤销时先撤掉最近的，这叫还原现场。

第二个坑是没注意到撤销指令也会产生“分支”。有人会把撤销操作也当成一个对象压入某种数据结构，导致后续计算k时把撤销指令本身也数进去了。想清楚题面后就知道，交易才入栈，撤销只是出栈动作，栈中永远不存撤销指令。

第三个坑是输出顺序。我用unordered_map存余额，最后直接遍历map输出，结果本地跑样例没问题，一提交就WA。原因很简单，哈希表的遍历顺序不保证有序，而题目要求按账户编号从小到大。这个坑特别隐蔽，因为小规模样例的遍历顺序碰巧是正确的，只有大数据才能暴露问题。

第四个坑是金额溢出。我把转账金额和余额都定义成了int，自测数据全在几百块范围内一切正常，结果换到官方正式数据直接出错。后来把所有金额相关的变量改成long long，一次通过。这道题里金额范围并没有给得很宽松，不要抱着侥幸心理用int。

5.2 常见错误速查表

这些错误有一个共同特点，就是都发生在“逻辑看似正确但边界处理不严谨”的位置。蓝桥杯的评测数据非常喜欢卡边界，一个不足k笔的撤销指令就能让只写了主流程的代码现出原形。

5.3 同类题的扩展与迁移

“交易账本”这个模型在竞赛里并不是孤例。它本质上是“带有回滚操作的线性执行序列”。类似的应用场景还有文字编辑器的撤销功能：用户每进行一次编辑就入栈，执行撤销就从栈顶弹出最近一次编辑，弹完再把整个文档状态回滚一步。两者的数据结构模型完全相同。

如果再往后做题，你还会遇到撤销操作也可以被撤销的变体。比如题目改成“撤销最近k条指令，而撤销指令本身也算一条指令”，那就不能再用简单栈来解决，需要引入可持久化数据结构，或者离线建依赖关系进行处理。这道国赛题没有要求到那个深度，但我建议手里有余力的同学往这个方向想一想，对理解递归和可持久化的思想会有很大帮助。

还有一个小技巧：如果你发现自己写的栈模拟代码在撤销时同时要维护很多余额变化，可以先把所有变化集中到一个函数里，入栈和出栈都调用它，只是参数取相反数，这样能减少大量重复代码。我在实现中虽然没有单独抽函数，但在实际工程和更复杂的题目里，这个习惯能显著降低出错概率。

5.4 赛前自测清单

每次写完这类题，提交之前我都建议按这个清单快速过一遍：

• 是否处理了k大于剩余交易数的情况？
• 回滚时是否弹出的是栈顶元素？
• 余额变量是否使用了够宽的数据类型？
• 最终输出是否对账户编号做了排序？
• 如果题目要求输出所有账户而不是只输出交易过的账户，代码是否覆盖？
• 自转账是否会被错误跳过？
• 多次撤销之间会不会出现重复回滚同一笔交易的情况？

这个清单看起来简单，但它能覆盖这道题几乎所有的失分点。我自己的习惯是把这份清单背下来，比赛时遇到“操作类”题目就直接套用，省去大量反复试错的时间。

今年的题目叫交易账本，明年的题目可能叫日志恢复，也可能叫文件同步，但底层要考的东西大概率还是这一套：用一个栈维护当前有效操作序列，入栈执行正操作，出栈执行逆操作。把这个模型吃透了，这一类题就都不会再让你卡壳。