CCF认证201912-4. 区块链

欢迎访问我的CCF认证考试题解目录哦

题目描述

算法设计

大模拟题，主要是要用好STL。我们使用vector<vector<int>> graph存储节点和边，用vector<vector<int>> ans存储每个结点当前的主链。关键是如何存储表示接收链和产生块的操作。我们使用map<int, unordered_map<int, array<vector<int>, 2>>> actions存储这样的操作，map的键表示时间，可以让这些操作按时间进行排序；unordered_map的键表示节点编号；array内是一个二维vector<int>，当索引为0时vector<int>存储要接收的链，当索引为1时vector<int>存储要产生的块编号，结构有些复杂，结合下图或许能够帮助你加深理解。

题目中涉及到的操作实质上一共有3种：接收其他节点传来的链、产生块、查询，同一时刻3种操作处理优先级依次递减。由于输入数据是按操作时刻递增给出的，因此我们可以将接收链操作和产生块操作推迟到遇到查询的操作时再实现。代码中添加了足够的注释，具体实现可见代码。

注意点

1. 同一时刻接收链、产生块、查询这3种操作处理优先级依次递减。
2. 同一时刻一个节点可能产生多个块

C++代码

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> graph(505);  //存储节点的边关系
vector<vector<int>> ans(505, {0});  //存储每个节点的主链
int n, m, t, k;
map<int, unordered_map<int, array<vector<int>, 2>>> actions;  //存储接收链和产生块操作
bool canAccept(const vector<int>& Old, const vector<int>& New) {  //其他节点传递过来的新链New能否被接受
    return Old.size() != New.size() ? Old.size() < New.size() : Old.back() > New.back();
}
void diffuse(int v, int time) {  //将节点v的主链广播出去
    for (int i : graph[v]) {
        auto& chain = actions[time][i][0];
        if ((chain.empty() and canAccept(ans[i], ans[v])) or (not chain.empty() and canAccept(chain, ans[v])))
            chain = ans[v];
    }
}
void query(int a, int b) {  //查询a节点在b时刻的主链
    for (auto& action : actions) {  //遍历所有接收链和产生块操作
        int curTime = action.first;
        if (curTime > b)  //当前操作时刻>b，结束循环
            break;
        for (auto& vertex : action.second) {
            int v = vertex.first;  //获取该操作节点编号
            auto &chain = vertex.second[0], &blocks = vertex.second[1];  //要接收的链、要产生的块
            bool canDiffuse = canAccept(ans[v], chain) or not blocks.empty();  //节点v是否要向外广播主链
            if (canAccept(ans[v], chain))  //先接收其他节点的主链
                ans[v] = chain;
            for (int b : blocks)  //再产生块
                ans[v].push_back(b);
            if (canDiffuse)  //向外广播
                diffuse(v, curTime + t);
        }
    }
    actions.erase(actions.begin(), actions.upper_bound(b));  //删除b时刻及其以前的所有操作，避免重复处理
    cout << ans[a].size();
    for (int i : ans[a])
        cout << " " << i;
    cout << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    cin >> t >> k;
    for (int i = 0; i < k; ++i) {
        int a, b, c;
        cin >> a >> b;
        if (cin.get() == '\n' or cin.eof()) {
            query(a, b);
        } else {
            cin >> c;
            actions[b][a][1].push_back(c);
        }
    }
    return 0;
}