CCF 201912-4 区块链 满分题解

问题分析

• 题目的大体意思是有一个无向图，每个节点有自己的主链，并且每个节点可以自己产生一个新的块添加到主链上，这就视为一次更新。
• 节点u在更新后，会将自己的主链发送给所有与它邻接的节点，这些节点经过一定的延迟interval后收到邻居节点u发来的主链，并与自己的主链相比较，如果满足比较条件，则会把收到的主链作为自己的主链，这也视为一次更新，更新后，将自己的主链发送给所有与它邻接的节点。
• 如此循环往复，其实就两个操作，更新、扩散、更新、扩散。

解题思路

1. 首先要构造一个无向图，用来存储每个节点和边的连通信息，这里我使用的链式前向星来存储，方便对一个节点的所有邻接点进行快速访问（如果对链式前向星不是特别了解，可以自行百度查阅一下，这是一个非常简单方便的数据结构）。每个节点相当于一条主链，可用vector数组进行存储，每个vector代表一个节点。

2. 我们可以将主链看做网络传输中发送的数据包，节点在产生块或收到邻居发来的包（主链）并更新后，会向邻居节点发送自己的包，这里假设发送时刻为t，链路延迟为interval，当前时刻为cur，那么邻居节点只有在t+interval=cur时才能恰好收到这个包，我们当然可以构造一个结构体

   struct Packet
   {
       vector<int> link;
       int t;
   };
   

   来存储这个包，其中link代表发送的主链，t代表送达时刻（即发送时刻+链路延迟interval），可以通过判断t是否小于cur来确定这个包是否已经过期。

3. 那么有人可能会想，那我用一个Packet类型的数组来存储每个节点发出的数据包，下标就代表这个节点编号，可以吗？答案是否定的！因为链路是有容量的，如果节点u在t时刻发送一个数据包后，又在t~t+interval的时间段内连续发送了多个数据包，这样所有的数据包都没有送达（或者说都在路上），那么我们用什么来存储这些数据包呢？可以用双向队列deque来存储（至于为什么是双向的，到后面就会知道）。每发送一个数据包，就从队列后端压入一个数据包，当数据包过期（t<cur）时，将它从队列中移出。

4. 使用map来存储时刻t到达的数据包都是由哪些发送方发送的，其中键为送达时刻t，值为一个集合set，保存所有发送方编号。

5. 因为每个节点每一秒都有可能收到数据包，因此我们需要写一个传递函数，来更新生成下一秒图的状态，遍历map[t]中所有节点u，使用que[u]更新u的所有邻居节点，当邻居节点被更新后，就发出数据包，为防止在循环中多次发送数据包，可以把该节点放入更新集合updateSet中，在函数运行结束前统一让他们发送数据包。

6. 每次查询（或生成块）前我们需要把图的状态传递到查询（或生成块）的时刻，即一直传递到t==cur时，再进行查询（或生成块）的操作。

解题代码

// 201912-4 区块链.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include <unordered_map>
#include <string.h> 
#define MAXN 510
#define MAXM 10010
#define umap unordered_map
using namespace std;
int cur; //当前时间
int interval;
umap<int, set<int>> mp; //存储t时刻抵达的数据包的所有发送方
vector<int> node[MAXN];

struct Packet
{
    vector<int> link;
    int t; //送达时刻
};

//数据包队列
deque<Packet> que[MAXN];
//数据包时刻队列
deque<int> tque;

//===========================链式前向星=======================================
int n, m, cnt, head[MAXN];//n个点，m条边
struct Edge
{
    int to;
    int next;
}edge[MAXM << 1];

void init()
{
    memset(head, -1, sizeof(head));

    for (int i = 1; i <= n; i++)
        node[i].push_back(0);
}

void addEdge(int u, int v)
{
    edge[cnt].to = v;
    edge[cnt].next = head[u]; //与这个边起点相同的上一条边的编号
    head[u] = cnt++; //更新以u为起点最后一条边的编号
}
//===========================================================================

void sendPacket(int i, int t) //发送节点i，发送时刻t
{
    Packet p = { node[i], t + interval };

    if (!que[i].empty() && que[i].back().t == p.t) //覆盖当前时刻发的上一个数据包
        que[i].pop_back();

    que[i].push_back(p);
    if (tque.empty() || tque.back() != p.t) //更新数据包时刻队列
        tque.push_back(p.t);
    mp[p.t].insert(i);
}

void transmitOneSec()
{
    cur++;
    if (tque.empty() || tque.front() != cur)return;
    tque.pop_front();
    set<int> updateSet;
    set<int>& s = mp[cur]; //s中为当前时刻所有发送方的编号
    for (auto& i: s) //i为发送端
    {
        while (que[i].front().t < cur)
            que[i].pop_front();

        for (int j = head[i]; ~j; j = edge[j].next)
        {
            int u = edge[j].to;

            //数据包（主链）
            vector<int>& link = que[i].front().link;

            if (node[u].size() < link.size() ||
                node[u].back() > link.back() && node[u].size() == link.size())
            {
                node[u] = link;
                updateSet.insert(u);
            }
        }
    }
    for (auto& u : updateSet)
        sendPacket(u, cur); //接收完邻居的数据包后向外传递数据包

    mp[cur].clear();
    updateSet.clear();
}

void transmitToCurrent(int t)
{
    //传递到当前时刻（每秒更新一次）
    while (t != cur)
        transmitOneSec();
}

//a在t时刻产生了编号为c的块
void generate(int a, int t, int c)
{
    transmitToCurrent(t);
    node[a].push_back(c);
    sendPacket(a, t);
}

void search(int a, int t)
{
    transmitToCurrent(t);
    cout << node[a].size() << " ";
    size_t size = node[a].size();
    for (int i = 0; i < size; i++)
    {
        cout << node[a][i];
        if (i != size - 1)
            cout << " ";
    }
    cout << endl;
}

int main()
{
    IOS
    cin >> n >> m;
    init();
    int u, v, k, a, b, c;
    for (int i = 0; i < m; i++)
    {
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }
    cur = 0;
    cin >> interval >> k;
    for (int i = 0; i < k; i++)
    {
        cin >> a >> b;
        if (cin.get() == '\n')
        {
            search(a, b);
        }
        else
        {
            cin >> c;
            generate(a, b, c);
        }
    }
}

附输入数据

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
1 27
1 1 1
2 1 2
3 1 3
4 1 4
5 1 5
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 10 10
2 11 9
1 11
2 11
3 11
4 11
5 11
1 12
2 12
3 12
4 12
5 12

15 13
1 2
2 3
3 4
4 5
1 6
6 7
7 8
8 9
1 10
10 11
11 12
12 13
14 15
6 28
1 1 1
1 2 2
1 6
2 7
13 7
9 7
5 7
3 14
8 14
5 14
11 14
9 25
5 25
13 25
9 29 3
5 29 4
13 29 5
1 53
2 59 6
2 59
1 1000
3 1000
8 1000
9 1000
10 1000
13 1000
14 1000
15 1000