CCF认证201912-4. 区块链
发布时间
阅读量：
阅读量
题目描述
算法设计
大规模模拟题需要用好STL库的技术实现。我们采用vector<vector
题目中具体包括三种操作：接收来自其他节点的链、生成区块以及查询；在同一时间点的三种操作中，处理优先级依次降低；基于此原因，在执行查询之前推迟对链的接收和块的生成；代码中增加了详细的注释说明，并在后续部分提供了具体的实现细节
C++代码
#include<iostream>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<cstdio>
#include<sstream>
#include<unordered_map>
#include<array>
//#include<bits/stdc++.h>
using namespace std;
int n, m, t, k;
vector<vector<int>> G(505);
vector<vector<int>>links(505, {0});
map<int, unordered_map<int, array<vector<int>, 2>>> mp;
bool canAccept(const vector<int> &Old, const vector<int> &New)
{
if (Old.size() < New.size()||(Old.size()==New.size()&&Old.back()>New.back()))
return true;
return false;
}
void diffuse(int v, int time)
{
for (int i : G[v])
{
auto &chain = mp[time][i][0];//
if (chain.empty() && canAccept(links[i], links[v]) || !chain.empty() && canAccept(chain, links[v]))
{
chain = links[v];//等效于chain=
}
}
}
void query(int a, int b)
{
//注意&的使用
for (auto& action : mp)//action 健为时间 会进行排序
{
int curTime = action.first;
if (curTime > b)
break;
for (auto &vertex : action.second)//先进行接受链操作
{
int v = vertex.first;//获取该操作节点编号
auto &chain = vertex.second[0];
auto &block = vertex.second[1];
bool is1 = false;
if (canAccept(links[v],chain))
is1 = true;
if (is1)
links[v] = chain;
bool is2 = false;
if (!block.empty())
is2 = true;
for (int b : block)
links[v].push_back(b);
if (is1||is2)
{
diffuse(v, curTime + t);
}
}
}
//删除b时刻及其以前的所有操作，避免重复处理
mp.erase(mp.begin(), mp.upper_bound(b));
cout << links[a].size();
for (int i : links[a])
{
cout << " " << i;
}
cout << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
/*G.resize(505);
links.resize(505, {0});*/
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[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' || cin.eof())
{
query(a, b);
}
else
{
cin >> c;
mp[b][a][1].push_back(c);
}
}
return 0;
}
/*
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
142. 143. 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
*/注意点
- 在同一时间段内进行的接收链条、生成数据块以及查询操作呈现处理优先级递减的趋势。
- 在一个时间段内同一个节点能够持续不断地生成多批次的数据块。
全部评论 (0)
还没有任何评论哟~