题目

题目

题解

官方题解

7-1 懂的都懂

分数 20

直接暴力

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 55, K = 260;
int f[N][K];//选i个数，平均值是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 芬兰木棋

这个题一开始读了假题，因为距离原点的距离不同，所以你要对她进行排序，然后不能存斜率，不能存斜率！！坑惨了，因为是四个象限，所以只能存gcd之后的数，而且gcd要加绝对值，要不然就会改变象限，注意它可以扔无限多次，也就是分数肯定都能拿到

分数 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 打怪升级

分数 25

这个emm，debug发现是一个小错，绝了，就是flody先找出发点，注意是每个最短路里面的最大值进行比较，从最大值里面选最小值！！

#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 疫情防控

分数 30

这个思路很重要，因为删除点是从前往后进行删除，删到后面的时候，前面的已经被删了，所以可以反过来，从最后一个开始往前加点，因为这样，从最后一个慢慢加到第一个的时候，当到第一个的时候，后面的肯定没删，然后发现这种做法也都加上了，就很巧妙！

#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;
}