CCF 201912-4 区块链 满分题解


CCF 201912-4 区块链 满分题解

CCF 201912-4 区块链 满分题解

问题分析

CCF 201912-4 区块链 满分题解

CCF 201912-4 区块链 满分题解

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

解题思路

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

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

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

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

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

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

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

    每次查询(或生成块)前我们需要把图的状态传递到查询(或生成块)的时刻,即一直传递到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

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

CCF 201912-4 区块链 满分题解

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » CCF 201912-4 区块链 满分题解
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏