CCF 201912-4 区块链

区块链

来源：CCF

标签：

参考资料：

相似题目：

题目

区块链涉及密码学、哈希算法、拜占庭问题、共识算法、故障模型、网络模型等诸多知识，也在金融等领域有广泛的应用。本题中，我们需要实现一个简单的区块链系统。
在一个分布式网络中，有n个节点通过m条边相连，节点编号从1至n。每个节点初始化都有一个相同的“创世块”，链长都为1，每个节点在整个过程中都需要维护一条主链，任何操作都只在主链上进行。在整个系统中产生的每个新块都有唯一的整数编号，创始块的编号为0，其余块的编号都为正整数。当某个节点的链更新时，会将它的主链发送给它相邻的节点（邻居）；而当节点收到链时，决定是否更新自己的主链下列情况可能会导致某个节点的链更新：
·某个节点接收到邻居发送过来的链，与当前自己的主链进行比较：如果接收到的链更长，则将其作为自己的主链；如果收到的链长度与自身主链相同，且最后一块编号更小，则将其作为自己的主链
如果接收到的链更短，则直接忽略该链。
·某个节点产生一个新块，将新块放在主链的尾部。
假设网络带宽足够大，每个节点状态更新后，会立刻将自己的主链同时发送给所有邻居。每个节点在每个时刻总是先接收链，再产生新块（注意这与实际的区块链工作方式不相同），每个节点发送、接收、产生块不消耗时间，只有在网络中传输链会消耗时间。不过因为一些故障，这个网络可能会出现“分区”的情况，即出现多个子网络，不同子网络的节点无法互相收发消息
在计算机中常用逻辑时钟来定义“时刻”，逻辑时钟初始时间为0，以单位1递增。任意节点传输一条链到其邻居所花费的时间相同，都为1。现在已知整个网络的结构以及每个节点产生新块的时间，需要查询特定时刻某个节点的主链。

输入

从标准输入读入数据。
保证题中所有输入均为整数，并且所有整数绝对值不大于10^9。
第一行两个正整数分别为n，m，分别表示网络的n个节点和m条边。
接下来m行，每行2个正整数ui，vi，（1<=i<=m），表示网络中节点ui和节点vi，具有（双向）连接。
接下来一行两个正整数t，k，分别表示每次传输延时，和操作（产生块或查询）的数量。
接下来k行，每行2或3个正整数：
如果是三个数a，b，c，表示节点a在b，时刻产生了一个编号为ci的块。保证bi<=bi+1（1<=i<=k）。
如果是两个数ai，bi，表示查询节点ai处理完bi时刻及以前的所有操作后的主链。保证对于同一时刻，任何查询在输入文件中都出现在当前时刻所有的新块被产生之后。

输出

输出到标准输出。
依次输出若干行，分别对应每一次查询。
每行第一个正整数L表示主链的长度，接下来L个数表示主链每个块的编号。从链头（一定为0）到链尾依次输出。

输入样例1

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

输出样例1

2 0 1
2 0 2
2 0 3
2 0 4
2 0 5
2 0 1
2 0 1
2 0 1
2 0 1
2 0 1
3 0 1 10
4 0 1 10 9
3 0 1 10
3 0 1 10
3 0 1 10
4 0 1 10 9
4 0 1 10 9
4 0 1 10 9
4 0 1 10 9
4 0 1 10 9

样例解释1

网络中的节点与连接关系形成一张完全图。在时刻1时，所有节点都产生一个块，所以查询结果主链长度都为2，主链更新后，将自己的主链发给所有邻居。
因为传输时间为1，所以在时刻2时，所有节点都收到其他节点发来的主链并更新，更新后发送新的主链给邻居。此时查询所有节点，主链都为01。
节点1在时刻10产生了新的块10，并发送给邻居。所有邻居在时刻11时接收到节点1发送的块10，同时，节点2在时刻11产生了新块11，所以，时刻11时的节点2主链长为4，其余节点主链长为3，所有发生更新的节点在时刻11时向邻居发送自己的主链。
所以在时刻12时，所有节点的主链长为4.

输入样例2

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

输出样例2

3 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

提示

解题思路

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N=505,M=5e4+5;
struct node{
    int len,val;
    node *nxt;
    node(int len=0,int val=0,node *nxt=NULL):len(len),val(val),nxt(nxt){}
}*p[N],*god,*tmp;
vector<int>e[N];int L,n,m,t,q,ans[M];
struct assign{
    node *u;
    int x,T;
    assign(node *a=NULL,int b=0,int c=0):u(a),x(b),T(c){} 
};
deque<assign>Q;
void ass_insert(int x,int T){
    for(int &i:e[x]) Q.push_back(assign(p[x],i,T+t));
}
void bfs(int lim){
    while(!Q.empty()&&Q.front().T<=lim){
        assign now=Q.front();
        if(now.u->len>p[now.x]->len||
          (now.u->len==p[now.x]->len&&now.u->val<p[now.x]->val)){
            p[now.x]=now.u;
            ass_insert(now.x,now.T);
        }
        Q.pop_front();
    }
}
void print(node *rt){
    printf("%d ",L=rt->len);
    for(int i=rt->len;i;i--,rt=rt->nxt) ans[i]=rt->val;
    for(int i=1;i<=L;i++) printf("%d ",ans[i]);puts("");
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0,x,y;i<m;i++) scanf("%d%d",&x,&y),e[x].emplace_back(y),e[y].emplace_back(x);
    god=new node(1,0);
    for(int i=1;i<=n;i++) p[i]=god;
    scanf("%d%d",&t,&q);
    for(int i=q,x,y,z;i;i--){
        scanf("%d%d",&x,&y);
        char ch=getchar();bool flag=0;
        if(ch!='
') flag=1,scanf("%d",&z);
        if(flag){
            bfs(y);
            tmp=new node(p[x]->len+1,z,p[x]);
            Q.push_front(assign(tmp,x,y));
        }
        else{
            bfs(y);
            print(p[x]);
        }
    }
    return 0;
}