CCF认证201912-4. 区块链

题目描述

算法设计

大模拟题，主要是要用好STL。我们使用vector<vector<int>> graph存储节点和边，用vector<vector<int>> ans存储每个结点当前的主链。关键是如何存储表示接收链和产生块的操作。我们使用map<int, unordered_map<int, array<vector<int>, 2>>> actions存储这样的操作，map的键表示时间，可以让这些操作按时间进行排序；unordered_map的键表示节点编号；array内是一个二维vector<int>，当索引为0时vector<int>存储要接收的链，当索引为1时vector<int>存储要产生的块编号，结构有些复杂，结合下图或许能够帮助你加深理解。

题目中涉及到的操作实质上一共有3种：接收其他节点传来的链、产生块、查询，同一时刻3种操作处理优先级依次递减。由于输入数据是按操作时刻递增给出的，因此我们可以将接收链操作和产生块操作推迟到遇到查询的操作时再实现。代码中添加了足够的注释，具体实现可见代码。

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


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
*/

注意点

1. 同一时刻接收链、产生块、查询这3种操作处理优先级依次递减。
2. 同一时刻一个节点可能产生多个块