CCF201912-4 区块链

好像还是大模拟题。。
熟练运用STL，知晓其底层所用实现效率即可。。。
跟算法倒是没多大关系。。。

因为输入的查询必定晚于输入相关节点生成，实际上确保了查询时刻升序。
为了实现查询给定时刻的状态，记录所有输入与中间的节点传输数据，直到查询时再模拟运行到查询时刻，剩下的不模拟直到下一个查询时刻输入。

链的传输操作（transmission）和新块的创建操作（creation），使用哈希表unordered_map记录。
考虑到操作记录的信息量比较大，怕爆空间，完成操作处理后，会将其从哈希表中擦除。

为了按时间顺序处理，同时保证高效率+记录的时间点不能重复，使用set记录了所有发生变化操作的时间点（timepoints）。
在模拟时，从timepoints中顺序取出，即可按照时间点顺序处理，然后查询是否有对应时刻的transmission与creation。
在完成相应时刻的模拟之后，会移除set中对应的时间点。这是为了后续再次查询时不会重复处理已经处理过的时间点。

虽然transmission和creation擦除后，对应时间点的操作记录已经为空，那么timepoints即使不擦除已处理元素，也不会再影响结果正确性。但是如果不擦除timepoints，遍历时间点时仍然会造成时运行时间上的浪费。
timepoints已处理过的时间点必须动态擦除，否则重复遍历已处理过的时间点，会导致程序运行时间超时。
注意STL容器erase方法的用法

代码长度 3.234KB
编程语言 C0X
评测结果 正确
得分 100
时间使用 3.328s
空间使用 16.00MB

#include <bits/stdc++.h>
using namespace std;

using nodeidT = int;
using chainT = vector<nodeidT>;
using broadcastMsg = pair<nodeidT, chainT>; // 发出节点ID，主链
vector<vector<nodeidT> > rel; // 节点-邻接表{相连节点...}
vector<chainT> chain;// 节点-主链{主链节点...}
unordered_map<int, vector<pair<nodeidT, int>>> creation; // 时间- {{节点，块编号}...}
unordered_map<int, vector<broadcastMsg> > transmission; // 时间- {节点，链{接收链组成节点...｝}...}
set<int> timepoints;

int n;
int delay;

inline void gen(int node, int t, int id) {
    creation[t].push_back({node, id});
    timepoints.insert(t);
}

inline void broadcastNeighbor(int node, int tp) {
    transmission[tp + delay].push_back({node, chain[node]});
    timepoints.insert(tp + delay); // 不要忘记维护时间点表
}

inline void query(int node, int t) {
    auto it = timepoints.begin();
    for (; it != timepoints.end() && *it <= t; ++it) {
        int tp = *it;
        // 先处理接收
        if (transmission.count(tp)) {
            for (const auto &msg: transmission[tp]) {
                const auto &fromid = msg.first;
                const auto &sentchain = msg.second;
                for (const auto &toid: rel[fromid]) {
                    if (chain[toid].size() < sentchain.size()
                        || (chain[toid].size() == sentchain.size() && chain[toid].back() > sentchain.back())
                            ) {
                        chain[toid] = sentchain; // 接受更新
                        broadcastNeighbor(toid, tp); // 向邻居广播自己的主链
                    }
                }
            }
        }
        transmission.erase(tp);
        // 处理创建
        if (creation.count(tp)) {
            for (const auto &p: creation[tp]) {
                const auto &nodeid = p.first;
                const auto &blockid = p.second;
                chain[nodeid].push_back(blockid); // 主链延长
                broadcastNeighbor(nodeid, tp); // 向邻居广播自己的主链
            }
        }
        creation.erase(tp);
    }
    timepoints.erase(timepoints.begin(), it); // 此处erase使用注意，不能在循环中擦除当前key，否则当前迭代器失效无法自增至下一元素
    // 输出该时间点状态
    cout << chain[node].size();
    for (int b: chain[node]) {
        cout << " " << b;
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    int m;
    cin >> n >> m;
    rel.resize(n + 1);
    chain.resize(n + 1, chainT(1, 0));
    creation.reserve(2000);
    transmission.reserve(2000);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        rel[u].push_back(v);
        rel[v].push_back(u);
    }
    int k;
    cin >> delay >> k;
    for (int i = 1; i <= k; ++i) {
        int a, b, c;
        cin >> a >> b;
        if (cin.get() == '\n' || cin.eof()) {
            query(a, b);
        } else {
            cin >> c;
            gen(a, b, c);
        }
    }
}

Donate