企业官网建设流程全解析

又到了刷真题的时间。这道 CSP-S 2022 的题，考点是哈希表。

题目来源：ACGO A49999 ｜ 洛谷 P8819
难度定位：省选/NOI- ｜ 通过率：47.77%

一、题目信息

题目名称：星战

所属赛事：2022 年 CSP-S 组复赛

官方难度：省选/NOI-

涉及知识点：哈希表

题目链接：https://www.acgo.cn/problemset/info/49999

洛谷编号：P8819（同一道题，两个平台均可提交，代码通用）

易错点（很多人栽在这）

• 按题意逐步实现时，把每个操作拆成独立步骤，别把多个条件揉进一个式子
• 规则里的『首次满足』『优先最早』这类措辞要落实成具体的比较顺序
• 高难度题的暴力分很关键，先写一版能过的部分分再想正解

题意简述

题意其实很直白：

在这一轮的星际战争中，我方在宇宙中建立了 n 个据点，以 m 个单向虫洞连接。我们把终点为据点 u 的所有虫洞归为据点 u 的虫洞。

战火纷飞之中这些虫洞很难长久存在，敌人的打击随时可能到来。这些打击中的有效打击可以分为两类：

1. 敌人会摧毁某个虫洞，这会使它连接的两个据点无法再通过这个虫洞直接到达，但这样的打击无法摧毁它连接的两个据点。
2. 敌人会摧毁某个据点，由于虫洞的主要技术集中在出口处，这会导致该据点的所有还未被摧毁的虫洞被一同摧毁。而从这个据点出发的虫洞则不会摧毁。

注意：摧毁只会导致虫洞不可用，而不会消除它的存在。

为了抗击敌人并维护各部队和各据点之间的联系，我方发展出了两种特种部队负责修复虫洞：

• A 型特种部队则可以将某个特定的虫洞修复。
• B 型特种部队可以将某据点的所有损坏的虫洞修复。

考虑到敌人打击的特点，我方并未在据点上储备过多的战略物资。因此只要这个据点的某一条虫洞被修复，处于可用状态，那么这个据点也是可用的。

我方掌握了一种苛刻的空间特性，利用这一特性我方战舰可以沿着虫洞瞬移到敌方阵营，实现精确打击。

为了把握发动反攻的最佳时机，指挥部必须关注战场上的所有变化，为了寻找一个能够进行反攻的时刻。总指挥认为：

• 如果从我方的任何据点出发，在选择了合适的路线的前提下，可以进行无限次的虫洞穿梭（可以多次经过同一据点或同一虫洞），那么这个据点就可以实现反击。
• 为了使虫洞穿梭的过程连续，尽量减少战舰在据点切换虫洞时的质能损耗，当且仅当只有一个从该据点出发的虫洞可用时，这个据点可以实现连续穿梭。
• 如果我方所有据点都可以实现反击，也都可以实现连续穿梭，那么这个时刻就是一个绝佳的反攻时刻。

总司令为你下达命令，要求你根据战场上实时反馈的信息，迅速告诉他当前的时刻是否能够进行一次反攻。

前置知识

这题要用到的工具不多，但有一个容易忘，先过一遍。

按题意一步步走

模拟题不考算法，考的是「把话翻译成代码」的耐心。读题时把变量、循环、边界一条条列出来，再动手写，比边写边想快得多。

二、思路分析

这题官方难度省选/NOI-，后半场，先写暴力再想正解比较稳妥。

思路的入口在哪里？

这道「星战」属于模拟类问题。拿不到官方题解的题，我们把推导过程还原一遍，重点是让你能自己想出来。

第一步，读清目标。题目要我们求什么？是求一个数值、一个方案，还是判断可行性？目标不同，做法差别很大。

第二步，看数据范围。数据范围往往直接告诉你该用什么复杂度的算法，这一步比想算法更重要。

第三步，从小规模入手。先手算题目给的样例，把中间过程写下来，规律往往就在这个过程中浮现。

第四步，落到模拟的标准套路。确定方向后，把题目条件翻译成代码结构，再处理边界。

下面给出的是一份可在 ACGO 与洛谷两平台提交的参考实现，建议先自己写一遍，再回来对照。

三、完整代码

#include <cstdio> #include <ctime> #include <cstdlib> using namespace std; // CSP-S 2022 星战 // n 个据点、m 个单向虫洞（边 (u,v) 表示从 u 出发到 v）。 // 四类操作： // 1 u v : 摧毁虫洞 (u,v) // 2 u : 摧毁据点 u（= 摧毁所有「以 u 为终点」且尚未摧毁的虫洞） // 3 u v : 修复虫洞 (u,v) // 4 u : 修复据点 u（= 修复所有以 u 为终点的虫洞） // 每次操作后判断能否「反攻」：当前所有可用虫洞构成的有向图，每个据点出度恰为 1 // （此时从任一点出发都永远走得下去）。输出 YES / NO。 // // 关键观察：能反攻 ⟺ 所有点出度恰好为 1。 // 用「和哈希（sum hash）」判定： // 给每个点一个随机权值 w[u]，记 tot = Σ w[u]； // 维护 ans = 当前所有可用虫洞起点的权值和， // 以及 r[v] = 当前所有指向 v 的可用虫洞起点的权值和（v 的「入边权值和」）， // 修复据点用的原始值存 r0[v]。 // 则「所有点出度为 1」的充要（高概率）条件为 ans == tot。 // 四类操作的 O(1) 维护： // 1 u v : r[v] -= w[u]; ans -= w[u] // 2 u : ans -= r[u]; r[u] = 0 // 3 u v : r[v] += w[u]; ans += w[u] // 4 u : ans += r0[u] - r[u]; r[u] = r0[u] // 用 unsigned long long 自然溢出（等价于 mod 2^64）。 const int MAXN = 500005; int n, m, q; unsigned long long w[MAXN]; unsigned long long r[MAXN], r0[MAXN]; unsigned long long tot = 0, ans = 0; int main() { srand((unsigned)time(0) * 1000003u + 12345u); scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) { // 64 位随机权值（拼接两次 rand 提高随机性） unsigned long long hi = (unsigned)rand(), lo = (unsigned)rand(); w[i] = (hi << 21) ^ (lo << 3) ^ ((unsigned long long)rand()); tot += w[i]; } for (int i = 1; i <= m; ++i) { int u, v; scanf("%d %d", &u, &v); r[v] += w[u]; ans += w[u]; } for (int i = 1; i <= n; ++i) r0[i] = r[i]; scanf("%d", &q); while (q--) { int t; scanf("%d", &t); if (t == 1) { int u, v; scanf("%d %d", &u, &v); r[v] -= w[u]; ans -= w[u]; } else if (t == 2) { int u; scanf("%d", &u); ans -= r[u]; r[u] = 0; } else if (t == 3) { int u, v; scanf("%d %d", &u, &v); r[v] += w[u]; ans += w[u]; } else { int u; scanf("%d", &u); ans += r0[u] - r[u]; r[u] = r0[u]; } puts(ans == tot ? "YES" : "NO"); } return 0; }

四、代码分段拆解

完整代码在上面，下面按功能分块解释。

头文件与全局变量

先把用到的头文件和全局变量放上来。全局变量在竞赛里很常用，好处是函数之间共享方便，代价是要小心初始化和被意外改写。

#include <cstdio> #include <ctime> #include <cstdlib>

using namespace std; const int MAXN = 500005; int n, m, q; int main() {

主体逻辑

主体部分按顺序完成读入、计算、输出。main函数尽量保持线性，把复杂的逻辑拆成独立函数，出问题时更容易定位。

边界处理

这类题最容易在边界上翻车：最小值、最大值、只剩一个元素的情况，都在脑中过一遍。

五、实例模拟

光看代码容易虚，用样例实测一遍最踏实。

样例 1

输入：

3 6 2 3 2 1 1 2 1 3 3 1 3 2 11 1 3 2 1 2 3 1 1 3 1 1 2 3 1 3 3 3 2 2 3 1 3 1 3 1 3 4 2 1 3 2

输出：

NO NO YES NO YES NO NO NO YES NO NO

以第一组样例为例，输入是3 6、2 3、2 1、1 2、1 3、3 1、3 2、11、1 3 2、1 2 3、1 1 3、1 1 2、3 1 3、3 3 2、2 3、1 3 1、3 1 3、4 2、1 3 2，正确输出是NO、NO、YES、NO、YES、NO、NO、NO、YES、NO、NO。建议把这两行数据抄在纸上，用上面的代码手动走一遍，重点看循环变量怎么变化、答案在哪一步被更新。能自己推出来的东西，比看懂代码印象深得多。

六、踩坑总结

最后总结几个要点。

1. 按题意逐步实现时，把每个操作拆成独立步骤，别把多个条件揉进一个式子
2. 规则里的『首次满足』『优先最早』这类措辞要落实成具体的比较顺序
3. 高难度题的暴力分很关键，先写一版能过的部分分再想正解

另外提醒一句：这题在 CSP-S 2022 里是省选/NOI-难度，考场上如果没有把握拿满分，先把暴力写法交上去拿到部分分，再回头优化。CSP 是打分制，空着不写才是最亏的。

七、知识点拓展

这题的核心是模拟。

模拟题在 CSP 里属于「必须拿满」的部分。它的训练价值不在于算法，而在于把一段自然语言描述准确翻译成代码的能力。训练方法很简单：读完题先不写代码，用中文把步骤一步步列出来，再逐条翻译。

建议的练习路径：

1. 先把本题独立写一遍，不看代码，遇到卡壳再看提示
2. 换个平台提交（ACGO 和洛谷都试试），确保代码在两个平台都能过
3. 找两到三道同类型的题练手，巩固这类问题的识别能力

八、适用人群

这道题的适用面：

• 目标是 CSP-S 高分或省选的同学
• 想通过真题理解高难度题如何从暴力优化到正解的同学
• 想弄明白模拟类问题标准解法的同学

代码有任何问题欢迎指正，我会及时更新。

关于这个系列

这是「CSP 真题逐题精讲」的第 33 篇。我会按年份从 2019 一路刷到 2025，
CSP-J 和 CSP-S 全覆盖。每篇都给：双平台题号（ACGO + 洛谷）+ 逐行代码拆解 + 真实样例模拟。

跟着刷完这一套，CSP 第一轮的选择题和基础题基本就稳了。

下一篇：CSP-S 2022 假期计划（提高+/省选-）

👉 关注我，不错过后续更新。评论区告诉我你现在刷到哪一年了，我看看能不能按大家的进度调整更新节奏。