区块链

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

用父指针共享链前缀，并按时刻合并到达消息后进行事件模拟。

OJ: shumeng

题目 ID: CSP201912D

难度:提高+/省选-

标签:图论模拟事件模拟链式结构

日期: 2026-07-31 16:21

形式化题目

$n$ 个节点通过无向边相连，每个节点维护一条从创世块 0 开始的主链：收到更长的链时替换，收到等长链时选择末块编号更小的链；产生一个新块时，把它接在当前主链末尾。一条链经过每条边都恰好延迟 $t$ 个逻辑时刻。给出按时间非递减排列的产生块和查询操作，模拟每个节点在查询时的主链。一个时刻内必须先接收所有链，再产生块；查询排在该时刻所有产生块之后。

思路

朴素做法

小数据暴力解直接在消息中复制完整的 vector<int> 链，保留相同的事件顺序，用于对拍。

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:41
 */
// brute.cpp：小数据直接模拟。消息中复制整条链，便于和正式解对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;

// 消息携带完整链：time 到达时刻，node 接收节点，chain 整条链的块编号序列。
struct Message {
    long long time;
    int node;
    vector<int> chain;
};

struct MessageOrder {
    bool operator()(const Message &left, const Message &right) const {
        return left.time > right.time;
    }
};

struct Operation {
    int node, block;
    long long time;
    bool is_query;
};

int n, m, delay_time;
vector<int> graph[MAXN], current_chain[MAXN], incoming_chain[MAXN];
bool received[MAXN];
priority_queue<Message, vector<Message>, MessageOrder> message_queue;

// 判断链 left 是否优于链 right；right 为空表示没有任何候选。
bool is_better(const vector<int> &left, const vector<int> &right) {
    if (right.empty()) return true;
    if (left.size() != right.size()) return left.size() > right.size();
    return left.back() < right.back();
}

void send_chain(int node, long long time) {
    for (int i = 0; i < (int)graph[node].size(); i++) {
        Message message = {time + delay_time, graph[node][i], current_chain[node]};
        message_queue.push(message);
    }
}

// 处理同一时刻到达的消息：先合并最优链，再统一更新并转发。
void process_messages(long long time) {
    vector<int> touched;
    while (!message_queue.empty() && message_queue.top().time == time) {
        Message message = message_queue.top();
        message_queue.pop();
        if (!received[message.node]) {
            received[message.node] = true;
            touched.push_back(message.node);
        }
        if (is_better(message.chain, incoming_chain[message.node])) {
            incoming_chain[message.node] = message.chain;
        }
    }
    for (int i = 0; i < (int)touched.size(); i++) {
        int node = touched[i];
        if (is_better(incoming_chain[node], current_chain[node])) {
            current_chain[node] = incoming_chain[node];
            send_chain(node, time);
        }
        incoming_chain[node].clear();
        received[node] = false;
    }
}

void print_chain(int node) {
    cout << current_chain[node].size();
    for (int i = 0; i < (int)current_chain[node].size(); i++) {
        cout << ' ' << current_chain[node][i];
    }
    cout << '\n';
}

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;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    int operation_count;
    cin >> delay_time >> operation_count;
    string line;
    getline(cin, line);

    vector<Operation> operations;
    for (int i = 0; i < operation_count; i++) {
        getline(cin, line);
        stringstream input(line);
        vector<long long> value;
        long long number;
        while (input >> number) value.push_back(number);
        Operation operation;
        operation.node = (int)value[0];
        operation.time = value[1];
        operation.is_query = value.size() == 2;
        operation.block = operation.is_query ? 0 : (int)value[2];
        operations.push_back(operation);
    }

    for (int i = 1; i <= n; i++) current_chain[i].push_back(0); // 创世块

    int operation_index = 0;
    while (operation_index < operation_count) {
        long long now = operations[operation_index].time;
        while (!message_queue.empty() && message_queue.top().time <= now) {
            process_messages(message_queue.top().time);
        }

        int end = operation_index;
        while (end < operation_count && operations[end].time == now) end++;
        vector<int> changed_nodes;
        for (int i = operation_index; i < end; i++) {
            if (operations[i].is_query) continue;
            int node = operations[i].node;
            current_chain[node].push_back(operations[i].block);
            changed_nodes.push_back(node);
        }
        sort(changed_nodes.begin(), changed_nodes.end());
        changed_nodes.erase(unique(changed_nodes.begin(), changed_nodes.end()), changed_nodes.end());
        for (int i = 0; i < (int)changed_nodes.size(); i++) {
            send_chain(changed_nodes[i], now);
        }
        for (int i = operation_index; i < end; i++) {
            if (operations[i].is_query) print_chain(operations[i].node);
        }
        operation_index = end;
    }

    return 0;
}

父指针共享链前缀

区块形成后，它和祖先的连接不会改变。把每个块保存为

text

1Block { parent, id, length }

其中 parent 是前一个块的下标。一个节点的主链只需记录末块下标；比较两条链时直接比较 length 和 id。输出时沿 parent 回溯并反转即可，不需要复制整条链。

事件模拟

消息写成事件 (到达时刻, 接收节点, 链末块)，用按到达时刻排序的最小堆维护。推进到一个操作时刻时，先处理所有已经到达的消息。同一时刻可能有多个邻居同时向同一节点发送链，因此先在 incoming_chain 中保留最优收到链，全部消息取完后才更新该节点并向邻居传播。这样不会依赖堆中同一时刻消息的弹出顺序。

当前时刻的产生块也要合并处理：新块的父亲是该节点接收阶段结束后的主链末块。同一节点如果有多个产生块，最后只发送一次最终主链；更早产生的链是它的前缀，单独发送不会改变任何接收者的最优结果。

样例时间线

下面的时间线来自样例 1。时刻 2 时，五个长度为 2 的链同时到达，各节点都选择末块编号最小的 1；时刻 11 中，节点 2 先收到 0,1,10，再接上新块 9。

时刻	产生块	查询
`1`	节点 `1` 到 `5` 分别产生块 `1` 到 `5`	查询五个节点
`2`	无	查询五个节点
`10`	节点 `1` 产生块 `10`	无
`11`	节点 `2` 产生块 `9`	查询五个节点
`12`	无	查询五个节点

正确性

父指针唯一地确定每个块及其所有祖先，因此它表示的链和题目中的主链完全一致，length 与末块编号也正好是比较规则需要的信息。对某个到达时刻，连续接收多条链后的最终状态一定是原主链和全部收到链中的最优者；先合并消息再更新恰好得到这个结果。每次主链变更都向所有邻居安排 $t$ 后的消息，故传播时刻与题意相同。按“接收、产生、查询”的次序处理每个时刻，输出的就是所询问时刻的主链。

代码

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:41
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;

// 一个区块：parent 是前一块下标，id 是题目给出的块编号，length 是所在链长度。
struct Block {
    int parent, id, length;
};

// 一条在途的链消息：time 是到达时刻，node 是接收节点，chain 是链的末块下标。
struct Message {
    long long time;
    int node, chain;
};

// 小根堆，按到达时刻从小到大取消息。
struct MessageOrder {
    bool operator()(const Message &left, const Message &right) const {
        return left.time > right.time;
    }
};

// 一条输入操作：产生块或查询。
struct Operation {
    int node, block;
    long long time;
    bool is_query;
};

int n, m, delay_time;
int current_chain[MAXN];  // 每个节点当前主链的末块下标
int incoming_chain[MAXN]; // 同一时刻收到的所有链中最好的一个，-1 表示尚未收到
vector<int> graph[MAXN];  // 无向图邻接表
vector<Block> blocks;     // 全部区块，下标即区块编号
priority_queue<Message, vector<Message>, MessageOrder> message_queue;

// 判断链 left 是否严格优于链 right；right == -1 表示没有任何候选。
bool is_better(int left, int right) {
    if (right == -1) return true;
    if (blocks[left].length != blocks[right].length) {
        return blocks[left].length > blocks[right].length;
    }
    return blocks[left].id < blocks[right].id;
}

// 节点 node 把末块为 chain 的链发给所有邻居，t 个时刻后到达。
void send_chain(int node, int chain, long long time) {
    for (int i = 0; i < (int)graph[node].size(); i++) {
        Message message = {time + delay_time, graph[node][i], chain};
        message_queue.push(message);
    }
}

// 处理所有在 time 时刻到达的消息：先合并出每个节点收到的最优链，再统一更新。
void process_messages(long long time) {
    vector<int> touched;
    while (!message_queue.empty() && message_queue.top().time == time) {
        Message message = message_queue.top();
        message_queue.pop();
        if (incoming_chain[message.node] == -1) touched.push_back(message.node);
        if (is_better(message.chain, incoming_chain[message.node])) {
            incoming_chain[message.node] = message.chain;
        }
    }
    for (int i = 0; i < (int)touched.size(); i++) {
        int node = touched[i];
        if (is_better(incoming_chain[node], current_chain[node])) {
            current_chain[node] = incoming_chain[node];
            send_chain(node, current_chain[node], time);
        }
        incoming_chain[node] = -1;
    }
}

// 沿父指针回溯整条链并正序输出。
void print_chain(int chain) {
    vector<int> answer;
    while (chain != -1) {
        answer.push_back(blocks[chain].id);
        chain = blocks[chain].parent;
    }
    reverse(answer.begin(), answer.end());
    cout << answer.size();
    for (int i = 0; i < (int)answer.size(); i++) cout << ' ' << answer[i];
    cout << '\n';
}

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;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    int operation_count;
    cin >> delay_time >> operation_count;
    string line;
    getline(cin, line);

    // 读入全部操作：两个数表示查询，三个数表示产生块。
    vector<Operation> operations;
    for (int i = 0; i < operation_count; i++) {
        getline(cin, line);
        stringstream input(line);
        vector<long long> value;
        long long number;
        while (input >> number) value.push_back(number);
        Operation operation;
        operation.node = (int)value[0];
        operation.time = value[1];
        operation.is_query = value.size() == 2;
        operation.block = operation.is_query ? 0 : (int)value[2];
        operations.push_back(operation);
    }

    Block genesis = {-1, 0, 1}; // 创世块 0，链长 1
    blocks.push_back(genesis);
    for (int i = 1; i <= n; i++) current_chain[i] = 0;
    fill(incoming_chain, incoming_chain + MAXN, -1);

    int operation_index = 0;
    while (operation_index < operation_count) {
        long long now = operations[operation_index].time;
        // 一个时刻内先处理所有已经到达的消息（接收阶段）。
        while (!message_queue.empty() && message_queue.top().time <= now) {
            process_messages(message_queue.top().time);
        }

        // 当前时刻的所有产生块：接在接收阶段确定的主链末尾。
        int end = operation_index;
        while (end < operation_count && operations[end].time == now) end++;
        vector<int> changed_nodes;
        for (int i = operation_index; i < end; i++) {
            if (operations[i].is_query) continue;
            int node = operations[i].node;
            Block block = {current_chain[node], operations[i].block,
                           blocks[current_chain[node]].length + 1};
            blocks.push_back(block);
            current_chain[node] = (int)blocks.size() - 1;
            changed_nodes.push_back(node);
        }
        // 同一节点产生多个块时只发送最终主链一次。
        sort(changed_nodes.begin(), changed_nodes.end());
        changed_nodes.erase(unique(changed_nodes.begin(), changed_nodes.end()), changed_nodes.end());
        for (int i = 0; i < (int)changed_nodes.size(); i++) {
            int node = changed_nodes[i];
            send_chain(node, current_chain[node], now);
        }
        // 查询排在当前时刻所有产生块之后。
        for (int i = operation_index; i < end; i++) {
            if (operations[i].is_query) print_chain(current_chain[operations[i].node]);
        }
        operation_index = end;
    }

    return 0;
}

复杂度

设实际发送的链消息数为 $S$ ，所有查询实际输出的块编号数为 $P$ 。消息堆操作的时间复杂度为 $O(S\log S)$ ，创建区块和读取操作为 $O(k)$ ，回溯输出为 $O(P)$ ，总时间复杂度 $O(S\log S + k + P)$ 。区块数不超过产生块操作数，空间复杂度为 $O(S+k)$ 。

总结

事件模拟中，最容易错的是同一时刻的先后关系。先把同一时刻到达消息合并成最优候选，再统一传播，可以严格对应“先接收、后产生”的规则。父指针既保留了每条历史链，又避免了每次消息复制整个链。

图示解析

这张图串起本题从输入操作到主链输出的主线：

text

1
2
3
4按时间分组的操作 + 延迟消息
`- 先合并同一时刻到达的最优链
   `- 节点更新后向邻居安排 time + t 的消息
      `- 产生块接到当前链尾，查询时沿 parent 回溯输出

先区分“消息到达”和“输入操作”两类事件。每个时刻只在接收阶段选一次最优链，之后的产生块必然接在该阶段确定的主链上。父指针让链状态可共享，传播时只传递末块编号。

时间限制： ~~10.0 秒~~ 2.0 秒

空间限制： 512 MB

题目描述

区块链涉及密码学、哈希算法、拜占庭问题、共识算法、故障模型、网络模型等诸多知识，也在金融等领域有广泛的应用。本题中，我们需要实现一个简单的区块链系统。

在一个分布式网络中，有 $n$ 个节点通过 $m$ 条边相连，节点编号从 $1$ 至 $n$ 。每个节点初始化都有一个相同的“创世块”，链长都为 $1$ 。每个节点在整个过程中都需要维护一条主链，任何操作都只在主链上进行。在整个系统中产生的每个新块都有唯一的整数编号，创始块的编号为 $0$ ，其余块的编号都为正整数。当某个节点的链更新时，会将它的主链发送给它相邻的节点（邻居）；而当节点收到链时，决定是否更新自己的主链。下列情况可能会导致某个节点的链更新：

某个节点接收到邻居发送过来的链，与当前自己的主链进行比较：
- 如果接收到的链更长，则将其作为自己的主链；
- 如果收到的链长度与自身主链相同，且最后一块编号更小，则将其作为自己的主链
- 如果接收到的链更短，则直接忽略该链。
某个节点产生一个新块，将新块放在主链的尾部。

假设网络带宽足够大，每个节点状态更新后，会立刻将自己的主链同时发送给所有邻居。每个节点在每个时刻总是先接收链，再产生新块（注意这与实际的区块链工作方式不相同）。每个节点发送、接收、产生块不消耗时间，只有在网络中传输链会消耗时间。不过因为一些故障，这个网络可能会出现“分区”的情况，即出现多个子网络，不同子网络的节点无法互相收发消息。

在计算机中常用逻辑时钟来定义“时刻”。逻辑时钟初始时间为 $0$ ，以单位 $1$ 递增。任意节点传输一条链到其邻居所花费的时间相同，都为 $t$ 。现在已知整个网络的结构以及每个节点产生新块的时间，需要查询特定时刻某个节点的主链。

输入格式

从标准输入读入数据。

保证题中所有输入均为整数，并且所有整数绝对值不大于 $10^9$ 。

第一行两个正整数分别为 $n, m$ ，分别表示网络的 $n$ 个节点和 $m$ 条边。

接下来 $m$ 行，每行 $2$ 个正整数 $u_i, v_i\ (1 \leq i \leq m)$ ，表示网络中节点 $u_i$ 和节点 $v_i$ 具有（双向）连接。保证网络中没有重复连接，但是可能会有 $u_i=v_i$ 的连接。

接下来一行两个正整数 $t, k$ ，分别表示每次传输延时 $t$ 和操作（产生块或查询）的数量。

接下来 $k$ 行，每行 $2$ 或 $3$ 个正整数：

如果是三个数 $a_i, b_i, c_i$ ，表示节点 $a_i$ 在 $b_i$ 时刻产生了一个编号为 $c_i$ 的块。
如果是两个数 $a_i, b_i$ ，表示查询节点 $a_i$ 处理完 $b_i$ 时刻及以前的所有操作后的主链。保证对于同一时刻，任何查询在输入文件中都出现在当前时刻所有的新块被产生之后。
保证所有操作的 $b_i \leq b_{i+1}\ (1 \leq i < k)$ ，所有产生块操作的 $c_i$ 互不相同。

输出格式

输出到标准输出。

依次输出若干行，分别对应每一次查询。

每行第一个正整数 $L$ 表示主链的长度，接下来 $L$ 个数表示主链每个块的编号。从链头（一定为 $0$ ）到链尾依次输出。

input1

output1

样例 1 解释

网络中的节点与连接关系形成一张完全图。在时刻 $1$ 时，所有节点都产生一个块，所以查询结果主链长度都为 $2$ 。主链更新后，将自己的主链发给所有邻居。

因为传输时间为 $1$ ，所以在时刻 $2$ 时，所有节点都收到其他节点发来的主链并更新，更新后发送新的主链给邻居。此时查询所有节点，主链都为 $0 1$ 。

节点 $1$ 在时刻 $10$ 产生了新的块 $10$ ，并发送给邻居。所有邻居在时刻 $11$ 时接收到节点 $1$ 发送的块 $10$ 。同时，节点 $2$ 在时刻 $11$ 产生了新块 $11$ 。所以，时刻 $11$ 时的节点 $2$ 主链长为 $4$ ，其余节点主链长为 $3$ 。所有发生更新的节点在时刻 $11$ 时向邻居发送自己的主链。

所以在时刻 $12$ 时，所有节点的主链长为 $4$ 。

input2

output2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
223 0 1 2
2 0 1
1 0
1 0
1 0
3 0 1 2
1 0
1 0
3 0 1 2
2 0 1
2 0 1
2 0 1
4 0 1 2 3
5 0 1 2 3 6
5 0 1 2 3 6
5 0 1 2 3 6
5 0 1 2 3 6
5 0 1 2 3 6
5 0 1 2 3 6
5 0 1 2 3 6
1 0
1 0

子任务

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	$n\le$	$m\le$	$t\le$	$k\le$	$L\le$
1	20	$10$	$30$	$10$	$500$	$30$
2	20	$50$	$100$	$100$	$5000$	$100$
3	20	$50$	$100$	$100$	$10^4$	$250$
4	20	$100$	$1000$	$100$	$3\times 10^4$	$350$
5	20	$500$	$10^4$	$1000$	$3\times 10^4$	$500$

在本评测链接中，保证所有数据的输出量不超过 10 MiB。

区块链

目录