2021robocom robot developer competition (Preliminary)

subject

subject

Answer key

Official explanation

7-1 Know everything.

fraction 20

Direct violence

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 55, K = 260;
int f[N][K];// choose i Number , The average is j
int vis[K];
int v[N];
int n, kk;

signed main()
{
    
	cin >> n >> kk;
	for(int i=1; i<=n; i++) cin >> v[i];
	
	for(int i=1; i<=n; i++)
		for(int j=i+1; j<=n; j++)
			for(int k=j+1; k<=n; k++)
				for(int p=k+1; p<=n; p++)
				{
    
					int t = v[i] + v[j] + v[k] + v[p];
					if(t % 4) continue;
					else t /= 4;
// cout << t << endl; 
					vis[t] = 1;
				}
	while(kk --)
	{
    
		int m, x; cin >> m;
		bool flag = 0;
		for(int i=1; i<=m; i++)
		{
    
			cin >> x;
			if(!vis[x]) flag = 1;
		}
		if(!flag) puts("Yes");
		else puts("No");
	}
	
	return 0;
}

7-2 Finnish wood chess

At the beginning of this question, I read a false question , Because the distance from the origin is different , So you have to sort her , Then you can't save the slope , Cannot save slope ！！ It's terrible , Because there are four quadrants , So you can only save gcd The number after , and gcd Add absolute value , Otherwise, it will change the quadrant , Note that it can be thrown infinitely many times , That is to say, you can definitely get scores
fraction 25

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 1e5 + 10;
#define PII pair<int, int>
#define INF 0x3f3f3f3f
#define x first
#define y second

map<PII, vector<PII> > v;
set<PII> s;
int n;

int gcd(int a, int b)
{
    
	return b ? gcd(b, a % b) : a;
} 

signed main()
{
    
	cin >> n;
	int a, b, c;
	
	for(int i=1; i<=n; i++)
	{
    
		cin >> a >> b >> c;
		int p = gcd(a, b);
		p = abs(p);
		v[{
    a / p, b / p}].push_back({
    a * a + b * b, c});
		s.insert({
    a / p, b / p});
	}
	
	int ans = 0;
	int res = 0;
	for(auto i : s)
	{
    
		int len = 0;
		sort(v[i].begin(), v[i].end());
		for(auto j : v[i])
		{
    
			if(j.y > 1) 
			{
    
				ans++;
				res += j.y;
				if(len) 
				{
    
					ans ++;
					len = 0;
				}
			}
			else 
			{
    
				len ++;
				res ++;
			}
		}
		if(len) ans ++;
	}
	
	cout << res << " " << ans << endl;
	return 0;
}

7-3 Have to upgrade

fraction 25
This emm,debug Discovery is a small mistake , great , Namely flody Find the starting point first , Note that the maximum value in each shortest circuit is compared , Choose the minimum from the maximum ！！

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
#define INF 0x3f3f3f3f
const int N = 1010;
int dist[N];
int val[N];
int mu[N];
int n, m;
int st[N];
int g[N][N], gg[N][N];
int v[N][N];
int pre[N];

void dij(int root)
{
    
	memset(dist, 0x3f, sizeof dist);
	memset(st,0,sizeof st);
	dist[root] = 0;
	val[root] = 0;
	for(int i=0; i<n; i++)
	{
    
		int t = -1;
		for(int j=1; j<=n; j++)
			if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
		
		st[t] = 1;

		for(int j=1; j<=n; j++) 
		{
    
			if(dist[j] > dist[t] + g[t][j])
			{
    
				dist[j] = dist[t] + g[t][j];
				val[j] = val[t] + v[t][j];
				pre[j] = t;
			}
			else if(dist[j] == dist[t] + g[t][j])
			{
    
				if(val[j] < val[t] + v[t][j])
				{
    
					val[j] = val[t] + v[t][j];
					pre[j] = t;
				}
			}
		}
	}
	
}
signed main()
{
    
	memset(g, 0x3f, sizeof g);
	
	cin >> n >> m;
	for(int i=1; i<=n; i++) g[i][i] = 0;
	
	int a, b, c, d;
	
	for(int i=1; i<=m; i++)
	{
    
		cin >> a >> b >> c >> d;
		v[a][b] = v[b][a] = d;
		g[a][b] = g[b][a] = c;
	}
	
	memcpy(gg, g, sizeof g);
	
	for(int kk=1; kk<=n; kk++)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				gg[i][j] = min(gg[i][j], gg[i][kk] + gg[kk][j]);
	
	int root = -1, maxn = INF;
	
	for(int i=1; i<=n; i++)
	{
    
		int tmp = 0;
		for(int j=1; j<=n; j++)
			tmp = max(tmp, gg[i][j]);
		if(tmp < maxn) 
		{
    
			maxn = tmp;
			root = i;
		}
	}
	
	cout << root << endl;
	
	dij(root);

	int k;
	cin >> k;
	for(int i=1; i<=k; i++) cin >> mu[i];
	vector<int> l;
	for(int i=1; i<=k; i++)
	{
    
		int rt = mu[i];
		l.clear();
		while(rt != root)
		{
    
			l.push_back(rt);
			rt = pre[rt];
		}
		
		reverse(l.begin(), l.end());
		cout << rt;
		
		for(auto i : l)
		{
    
			cout << "->" << i;
		}
		cout << endl;
		
		cout << dist[mu[i]] << " " << val[mu[i]] << endl;
	}
	
	return 0;
}

7-4 Epidemic prevention and control

fraction 30

This idea is very important , Because the deletion point is deleted from front to back , When deleted to the back , The previous one has been deleted , So it can be reversed , Start with the last one and add a little more , Because of this , From the last to the first , When it comes to the first , The following ones must not be deleted , Then I found that this practice was also added , It's clever ！

#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
//#define int long long
#define PII pair<int, int>
#define x first
#define y second
const int N = 5e4 + 10, M = 2e5 + 10, D = 1e3 + 10;
int n, m, c, q, d;
vector<int> v[N];
vector<PII> query[D];
int p[N];
bool vis[N];
int id[N];
int ans[N];
int find(int x)
{
    
	if(x != p[x]) p[x] = find(p[x]);
	return p[x];
}

void merge(int a, int b)
{
    
	a = find(a);
	b = find(b);
	
	if(a != b) p[a] = b;
}

signed main()
{
    
	cin >> n >> m >> d;
	int a, b;
	for(int i=1; i<=n; i++) p[i] = i;
	for(int i=1; i<=m; i++)
	{
    
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	
	for(int i=1; i<=d; i++)
	{
    
		cin >> c >> q;
		id[i] = c;
		vis[c] = 1;
		for(int j=1; j<=q; j++)
		{
    
			cin >> a >> b;
			query[i].push_back({
    a, b});
		}
	}
	
	for(int i=1; i<=n; i++)
		if(!vis[i])
			for(auto j : v[i])
				if(!vis[j]) merge(i, j);
	
	for(int i=d; i>=1; i--)
	{
    
		for(auto j : query[i])
		{
    
			a = find(j.x);
			b = find(j.y);
			if(a != b) ans[i] ++;
		}
		
		vis[id[i]] = 0;
		for(auto j : v[id[i]])
			if(!vis[j]) merge(id[i], j);
	}
	
	for(int i=1; i<=d; i++) cout << ans[i] << endl; 
	return 0;
}