[CSP-S 2022] 星战

GitHub跳转原题关系图返回列表

给每个据点一个 64 位权值，用全图可用虫洞的权值和维护出度状态，判断是否所有据点出度恰好为 1。

OJ: luogu

题目 ID: P8819

难度:提高+/省选-

标签:图论哈希模拟

创建: 2026-07-06 08:46

更新: 2026-10-07 10:45

形式化题目

给定一张 $n$ 个据点、 $m$ 条有向虫洞的图，初始时所有虫洞都可用。虫洞按终点归组：终点为 $v$ 的全部虫洞称为据点 $v$ 的虫洞。

依次执行 $q$ 条指令：

$t=1$ ：摧毁虫洞 $u\to v$ ；
$t=2$ ：摧毁据点 $v$ 的全部虫洞（即所有终点为 $v$ 的虫洞）；
$t=3$ ：修复虫洞 $u\to v$ ；
$t=4$ ：修复据点 $v$ 的全部虫洞。

每次指令执行后，判断当前时刻能否反攻。

反攻要求两件事同时成立：

实现反击：从任一据点出发都能无限穿梭（可重复经过同一据点或虫洞）；
实现连续穿梭：每个据点恰好只有一条可用虫洞从它出发。

条件 2 明确给出“每个据点的可用出度恰好为 $1$ ”。而一旦每个据点出度都恰好为 $1$ ，从任意据点走每一步都只有一条出边可选，图是有限的，必然走进一个环，从而可以无限穿梭，条件 1 自动满足。

因此判定条件可以压缩成一句话：

\text{每个据点当前的可用出度恰好等于 } 1.

暴力解法

思路

用二维数组记录每条虫洞是否存在、是否可用，每次指令后扫描所有据点统计出度，判断是否全部等于 $1$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 22:28
 * update_at: 2026-10-01 22:28
 */
// brute.cpp：小数据暴力解，逐条维护虫洞是否可用，每次指令后重新统计各据点出度。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 35;   // 暴力只服务小数据，n 取到 30 左右

int n, m, q;
bool exist_edge[MAXN][MAXN]; // exist_edge[u][v]：原图是否存在虫洞 u -> v
bool active_edge[MAXN][MAXN]; // active_edge[u][v]：虫洞 u -> v 当前是否可用

// 反攻时刻要求每个据点恰好有一条可用出边。
bool can_counterattack() {
    for (int u = 1; u <= n; u++) {
        int out_degree = 0;
        for (int v = 1; v <= n; v++) {
            if (active_edge[u][v]) {
                out_degree++;
            }
        }
        if (out_degree != 1) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        exist_edge[u][v] = true;
        active_edge[u][v] = true;
    }

    cin >> q;
    while (q--) {
        int type;
        cin >> type;

        if (type == 1) {
            // 摧毁虫洞 u -> v。
            int u, v;
            cin >> u >> v;
            active_edge[u][v] = false;
        } else if (type == 2) {
            // 摧毁据点 v 的全部虫洞，即终点为 v 的那些。
            int v;
            cin >> v;
            for (int u = 1; u <= n; u++) {
                if (exist_edge[u][v]) {
                    active_edge[u][v] = false;
                }
            }
        } else if (type == 3) {
            // 修复虫洞 u -> v。
            int u, v;
            cin >> u >> v;
            if (exist_edge[u][v]) {
                active_edge[u][v] = true;
            }
        } else {
            // 修复据点 v 的全部虫洞。
            int v;
            cin >> v;
            for (int u = 1; u <= n; u++) {
                if (exist_edge[u][v]) {
                    active_edge[u][v] = true;
                }
            }
        }

        cout << (can_counterattack() ? "YES" : "NO") << '\n';
    }

    return 0;
}

复杂度

每次指令后重新统计出度是 $O(n^2)$ （用邻接矩阵时），总时间复杂度 $O(qn^2)$ ，空间 $O(n^2)$ 。

瓶颈

$n,m,q$ 都可以到 $5\times10^5$ ， $O(qn^2)$ 完全不可行。真正的困难在于： $t=2$ / $t=4$ 这两条指令会成批改动“终点为 $v$ 的所有虫洞”，而每条虫洞的源点出度各不相同，逐条更新无法避免线性代价。

所以必须换一种表示：不再记录每个据点出度的精确数值，而是用一个全局聚合量间接判断“是否所有出度都等于 $1$ ”。

正解

思路

用权值和代表出度向量

给每个据点 $u$ 一个固定 64 位权值 $w[u]$ 。把每条当前可用的虫洞 $u\to v$ 记作对全局贡献 $w[u]$ ，那么全图的贡献和是

current=\sum_{u} w[u]\cdot outdeg(u),

其中 $outdeg(u)$ 是据点 $u$ 当前的可用出度。

如果所有出度都恰好为 $1$ ，那么

current=\sum_u w[u]=target.

反过来，若某个据点出度不是 $1$ ，则

current-target=\sum_u w[u]\cdot(outdeg(u)-1)

是一个非零整数线性组合。只要 $w[u]$ 取得足够“随机”，这个组合撞上 $0$ 的概率就极低。用 64 位哈希时， $5\times10^5$ 次询问里出现一次碰撞的概率约 $2.7\times10^{-14}$ ，在竞赛里可以接受。

代码用 splitmix64 把编号打散成权值，并刻意选用 unsigned long long：哈希依赖 $2^{64}$ 的自然回绕来做模运算，而有符号溢出是未定义行为，不能当取模用。

为什么还要维护每终点的入边和

$t=2$ / $t=4$ 要批量改动“终点为 $v$ 的全部虫洞”。如果只维护一个全局 current_sum，就没法一次把这批虫洞的贡献扣掉。于是再维护两个数组：

$full\_in\_sum[v]$ ：原图中所有终点为 $v$ 的虫洞的源点权值和；
$cur\_in\_sum[v]$ ：当前可用、终点为 $v$ 的虫洞的源点权值和。

四条指令就都变成常数次加减：

指令	对 `current_sum` 的改动	对 `cur_in_sum` 的改动
$t=1$ ：摧毁 $u\to v$	$-\ w[u]$	$cur\_in\_sum[v]\mathrel{-}=w[u]$
$t=2$ ：摧毁据点 $v$	$-\ cur\_in\_sum[v]$	$cur\_in\_sum[v]\leftarrow 0$
$t=3$ ：修复 $u\to v$	$+\ w[u]$	$cur\_in\_sum[v]\mathrel{+}=w[u]$
$t=4$ ：修复据点 $v$	$+\ (full\_in\_sum[v]-cur\_in\_sum[v])$	$cur\_in\_sum[v]\leftarrow full\_in\_sum[v]$

每次指令后只需判断 $current\_sum == target\_sum$ 。

与代码的对应

行内变量	含义
`value_of_node[u]`	据点 $u$ 的权值 $w[u]$
`full_in_sum[v]`	$full\_in\_sum[v]$
`cur_in_sum[v]`	$cur\_in\_sum[v]$
`target_sum`	$\sum_u w[u]$
`current_sum`	当前全图贡献和

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 22:28
 * update_at: 2026-10-01 22:28
 */
// main.cpp：给每个据点一个 64 位权值，用全图可用边的权值和判断是否所有据点出度恰好为 1。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 500005;   // n <= 5e5

int n, m, q;

// 权值数组用 unsigned long long，因为哈希要依赖 2^64 的自然回绕做模运算。
// 这里刻意选无符号：有符号溢出是未定义行为，无法当作取模。
unsigned long long value_of_node[MAXN]; // value_of_node[u]：据点 u 的固定权值
unsigned long long full_in_sum[MAXN];   // full_in_sum[v]：原图中所有终点为 v 的虫洞的源点权值和
unsigned long long cur_in_sum[MAXN];    // cur_in_sum[v]：当前可用、终点为 v 的虫洞的源点权值和
unsigned long long target_sum;          // 所有据点出度都恰好为 1 时的全图贡献和
unsigned long long current_sum;         // 当前可用虫洞的全图贡献和

// splitmix64：把一个整数打散成 64 位权值，只是为了让不同据点的权值互不相关。
unsigned long long splitmix64(unsigned long long x) {
    x += 0x9e3779b97f4a7c15ULL;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (ll i = 1; i <= n; i++) {
        value_of_node[i] = splitmix64(i);
        target_sum += value_of_node[i];
    }

    // 一条可用虫洞 u -> v 贡献 value_of_node[u]，于是
    // current_sum = sum( value_of_node[u] * 据点 u 当前的出度 )。
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        full_in_sum[v] += value_of_node[u];
        cur_in_sum[v] += value_of_node[u];
        current_sum += value_of_node[u];
    }

    cin >> q;
    while (q--) {
        ll type;
        cin >> type;

        if (type == 1) {
            // 摧毁虫洞 u -> v，它对全图贡献 value_of_node[u]。
            ll u, v;
            cin >> u >> v;
            cur_in_sum[v] -= value_of_node[u];
            current_sum -= value_of_node[u];
        } else if (type == 2) {
            // 摧毁据点 v 的全部虫洞，也就是终点为 v 的所有可用虫洞。
            ll v;
            cin >> v;
            current_sum -= cur_in_sum[v];
            cur_in_sum[v] = 0;
        } else if (type == 3) {
            // 修复虫洞 u -> v。
            ll u, v;
            cin >> u >> v;
            cur_in_sum[v] += value_of_node[u];
            current_sum += value_of_node[u];
        } else {
            // 修复据点 v 的全部虫洞，恢复成原图中终点为 v 的那批。
            ll v;
            cin >> v;
            current_sum += full_in_sum[v] - cur_in_sum[v];
            cur_in_sum[v] = full_in_sum[v];
        }

        if (current_sum == target_sum) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }

    return 0;
}

复杂度

时间复杂度：初始化 $O(n+m)$ ，每次指令 $O(1)$ ，总计 $O(n+m+q)$ 。
空间复杂度： $O(n)$ ，只存三个权值数组和几个全局量。

总结

这题的题意可以先压缩成一句话：每个据点当前可用出度恰好为 $1$ 。两个看似不同的条件——“能无限穿梭”和“恰好一条可用出边”——后者成立时前者必然成立。

优化的真正难点不在判定，而在于 $t=2$ / $t=4$ 会成批改动终点相同的虫洞。解法是不再维护出度向量本身，而是用每个据点一个 64 位权值把出度向量压成一个标量：

全局 current_sum 代表 $\sum_u w[u]\cdot outdeg(u)$ ；
每终点的 cur_in_sum[v] 让批量修改降成一次加减。

这类“用随机权值把集合/计数状态压成哈希和”的技巧，在需要支持批量增删、只问整体状态是否符合某个模式的题目里非常通用。代价是答案带极小的碰撞概率，属于随机化算法。

本文的 main.cpp 已用逐条统计出度的 brute.cpp 对拍 $300$ 组随机数据，题面样例通过。

P8819 [CSP-S 2022] 星战

题目描述

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

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

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

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

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

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

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

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

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

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

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

输入格式

输入的第一行包含两个正整数 $n,m$ 。

接下来 $m$ 行每行两个数 $u,v$ ，表示一个从据点 $u$ 出发到据点 $v$ 的虫洞。保证 $u \ne v$ ，保证不会有两条相同的虫洞。初始时所有的虫洞和据点都是完好的。

接下来一行一个正整数 $q$ 表示询问个数。

接下来 $q$ 行每行表示一次询问或操作。首先读入一个正整数 $t$ 表示指令类型：

若 $t = 1$ ，接下来两个整数 $u, v$ 表示敌人摧毁了从据点 $u$ 出发到据点 $v$ 的虫洞。保证该虫洞存在且未被摧毁。
若 $t = 2$ ，接下来一个整数 $u$ 表示敌人摧毁了据点 $u$ 。如果该据点的虫洞已全部被摧毁，那么这次袭击不会有任何效果。
若 $t = 3$ ，接下来两个整数 $u, v$ 表示我方修复了从据点 $u$ 出发到据点 $v$ 的虫洞。保证该虫洞存在且被摧毁。
若 $t = 4$ ，接下来一个整数 $u$ 表示我方修复了据点 $u$ 。如果该据点没有被摧毁的虫洞，那么这次修复不会有任何效果。

在每次指令执行之后，你需要判断能否进行一次反攻。如果能则输出 YES 否则输出 NO。

输出格式

输出一共 $q$ 行。对于每个指令，输出这个指令执行后能否进行反攻。

输入输出样例 #1

输入 #1

text

输出 #1

text

1
2
3
4
5
6
7
8
9
10
11NO
NO
YES
NO
YES
NO
NO
NO
YES
NO
NO

说明/提示

【样例解释 #1】

虫洞状态可以参考下面的图片, 图中的边表示存在且未被摧毁的虫洞：

【样例 #2】

见附件中的 galaxy/galaxy2.in 与 galaxy/galaxy2.ans。

【样例 #3】

见附件中的 galaxy/galaxy3.in 与 galaxy/galaxy3.ans。

【样例 #4】

见附件中的 galaxy/galaxy4.in 与 galaxy/galaxy4.ans。

【数据范围】

对于所有数据保证： $1 \le n \le 5 \times {10}^5$ ， $1 \le m \le 5 \times {10}^5$ ， $1 \le q \le 5 \times {10}^5$ 。

测试点	$n \le$	$m \le$	$q \le$	特殊限制
$1 \sim 3$	$10$	$20$	$50$	无
$4 \sim 8$	${10}^3$	${10}^4$	${10}^3$	无
$9 \sim 10$	$5 \times {10}^5$	$5 \times {10}^5$	$5 \times {10}^5$	保证没有 $t = 2$ 和 $t = 4$ 的情况
$11 \sim 12$	$5 \times {10}^5$	$5 \times {10}^5$	$5 \times {10}^5$	保证没有 $t = 4$ 的情况
$13 \sim 16$	${10}^5$	$5 \times {10}^5$	$5 \times {10}^5$	无
$17 \sim 20$	$5 \times {10}^5$	$5\times 10^5$	$5 \times {10}^5$	无