1. 首页
  2. 文章中心
  3. Other

AtCoder Grand Contest 010 题解

96 阅读 0 评论
我是靠谱客的博主 搞怪小土豆，最近开发中收集的这篇文章主要介绍AtCoder Grand Contest 010 题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A - Addition

如果奇数的个数是奇数就无解，否则就有解。

//waz
#include <bits/stdc++.h>
 
using namespace std;
 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
 
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
 
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
 
int F()
{
	char ch;
	int x, a;
	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
	if (ch == '-') ch = getchar(), a = -1;
	else a = 1;
	x = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + ch - '0';
	return a * x;
}
 
int n, ans; 
 
int main()
{
	gi(n);
	for (int i = 1; i <= n; ++i)
	{
		int x = F();
		if (x & 1) ++ans;
	}
	if (ans & 1) puts("NO");
	else puts("YES");
}

　　

B - Boxes

模拟，计算出以这个开头的操作有多少次，然后判断一下是不是可以完成。

//waz
#include <bits/stdc++.h>
 
using namespace std;
 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
 
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
 
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
 
int F()
{
	char ch;
	int x, a;
	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
	if (ch == '-') ch = getchar(), a = -1;
	else a = 1;
	x = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + ch - '0';
	return a * x;
}
 
int64 n, a[100010], b[100010], x[100010];
 
int64 s = 0;
 
int main()
{
	gi(n);
	for (int i = 1; i <= n; ++i) gi(a[i]), s += a[i];
	if (s % ((n + 1LL) * n / 2) != 0)
	{
		puts("NO");
		return 0;
	}
	s /= ((n + 1LL) * n / 2);
	int64 all = s, allx = s * (n - 1);
	for (int i = 1; i <= n; ++i)
	{
		if ((s + a[i] - a[i % n + 1]) % n != 0)
		{
			puts("NO");
			return 0;
		}
		int64 y = (s + a[i] - a[i % n + 1]) / n;
		int64 x = s - y;
		if (y > all || x > allx)
		{
			puts("NO");
			return 0;
		}
		all -= y;
		allx -= x;
		b[i % n + 1] = y;
	}
	if (all || allx) return puts("NO"), 0;
	int64 cnt = 0, tag = 0;
	for (int i = 1; i <= n; ++i)
	{
		cnt += b[i];
		tag += cnt;
		x[i] += tag;
		if (x[i] > a[i])
		{
			puts("NO");
			return 0;
		}
	}
	for (int i = 1; i <= n; ++i)
	{
		cnt -= b[i];
		tag += cnt;
		if (b[i]) tag -= n * (b[i]);
		x[i] += tag;
		//cerr << x[i] << endl;
		if (x[i] != a[i])
		{
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	return 0; 
}

　　

C - Cleaning

对于每一个非叶节点，所有的覆盖都至少有一个端点在自己的子树里，要么两个都是，要么只有一个，计算一下情况，转移上去，判断即可。

//waz
#include <bits/stdc++.h>
 
using namespace std;
 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
 
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
 
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
 
int F()
{
	char ch;
	int x, a;
	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
	if (ch == '-') ch = getchar(), a = -1;
	else a = 1;
	x = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + ch - '0';
	return a * x;
}
 
const int N = 1e5 + 10;
 
int n, deg[N];
 
int64 A[N];
 
VI edge[N];
 
void dfs(int u, int fa)
{
	if (deg[u] <= 1) return;
	int64 x = 0, cnt = 0, la = 0;
	for (auto v : edge[u])
	{
		if (v == fa) continue;
		dfs(v, u);
		x += A[v];
		la = max(la, A[v]);
	}
	cnt = min(x >> 1, x - la);
	if (x >= A[u] && x <= A[u] + cnt)
	{
		int64 c = x - A[u];
		A[u] -= c;
	}
	else
	{
		puts("NO");
		exit(0);
	}
}
 
int main()
{
	gi(n);
	for (int i = 1; i <= n; ++i) gi(A[i]);
	for (int i = 1; i < n; ++i)
	{
		int a, b;
		gii(a, b);
		edge[a].pb(b);
		edge[b].pb(a);
		++deg[a], ++deg[b];
	}
	if (n == 2)
	{
		puts(A[1] == A[2] ? "YES" : "NO");
		return 0;
	} 
	int root = 1;
	for (; deg[root] == 1; ++root);
	dfs(root, 0);
	if (!A[root]) puts("YES");
	else puts("NO");
}

　　

D - Decrementing

如果不考虑除以gcd的问题，就是sigma(A[i])-n的奇偶来判断胜负，如果有gcd，但如果是奇数，先手肯定必胜，否则看看先手能不能想办法除以2改变奇偶。递归下去交换先后手到一个不能改变的状态就好了。

//waz
#include <bits/stdc++.h>
 
using namespace std;
 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
 
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
 
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
 
int F()
{
	char ch;
	int x, a;
	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
	if (ch == '-') ch = getchar(), a = -1;
	else a = 1;
	x = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + ch - '0';
	return a * x;
}
 
const int N = 1e5 + 10;
 
int n, a[N];
 
void dfs(int x)
{
	long long s = 0;
	for (int i = 1; i <= n; ++i) 
		s += a[i] - 1;
	if (s & 1)
	{
		puts(x ? "Second" : "First");
		return;
	} 
	int cnt = 0;
	for (int i = 1; i <= n; ++i)
		if (a[i] & 1) ++cnt;
	for (int i = 1; i <= n; ++i)
		if (a[i] == 1) cnt = 233;
	if (cnt != 1)
	{
		puts(x ? "First" : "Second");
		return;
	}
	for (int i = 1; i <= n; ++i) 
		if (a[i] & 1) --a[i];
	int v = 0;
	for (int i = 1; i <= n; ++i) v = __gcd(v, a[i]);
	for (int i = 1; i <= n; ++i) a[i] /= v;
	dfs(x ^ 1);
}
 
int main()
{
	gi(n);
	for (int i = 1; i <= n; ++i) gi(a[i]);
	dfs(0);
}

　　

E - Rearranging

我们发现不互质的数相对位置不会改变，那么建出图来，先按从小到大遍历出一个DAG，从大到小跑拓扑序即可。

//waz
#include <bits/stdc++.h>
 
using namespace std;
 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
 
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
 
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
 
int F()
{
	char ch;
	int x, a;
	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
	if (ch == '-') ch = getchar(), a = -1;
	else a = 1;
	x = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + ch - '0';
	return a * x;
}
 
const int N = 2010;
 
int n, a[N], t[N][N], deg[N];
 
bool vis[N];
 
VI edge[N];
 
void dfs(int u)
{
	vis[u] = 1;
	for (int j = 1; j <= n; ++j)
		if (!vis[j] && t[u][j])
			edge[u].pb(j), ++deg[j], dfs(j);
}
 
priority_queue<int> pq;
 
int main()
{
	gi(n);
	for (int i = 1; i <= n; ++i) gi(a[i]);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			if (__gcd(a[i], a[j]) != 1)
				t[i][j] = 1;
	for (int i = 1; i <= n; ++i)
		if (!vis[i]) dfs(i);
	for (int i = 1; i <= n; ++i) if (!deg[i]) pq.push(i);
	while (!pq.empty())
	{
		int u = pq.top(); pq.pop();
		printf("%d ", a[u]);
		for (auto v : edge[u])
		{
			--deg[v];
			if (!deg[v]) pq.push(v);
		}
	}
	return 0;
}

　　

F - Tree Game

我们发现只有a[u]>a[v]的(u,v)才能走，否则两个人来回最后还是在原点不能动，所以建出(a[u]>a[v])的图，必败态就是没有出边了，所以对于每个点O(n) dfs一下即可。

//waz
#include <bits/stdc++.h>
 
using namespace std;
 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
 
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
 
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
 
int F()
{
	char ch;
	int x, a;
	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
	if (ch == '-') ch = getchar(), a = -1;
	else a = 1;
	x = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + ch - '0';
	return a * x;
}
 
const int N = 3010;
 
int n, a[N];
 
vector<int> edge[N];
 
bool dfs(int u, int fa)
{
	bool ret = 0;
	for (auto v : edge[u])
	{
		if (v == fa) continue;
		if (a[u] > a[v]) ret |= dfs(v, u) ^ 1;
	}
	return ret;
}
 
int main()
{
	gi(n);
	for (int i = 1; i <= n; ++i) gi(a[i]);
	for (int i = 1; i < n; ++i)
	{
		int u, v;
		gii(u, v);
		edge[u].pb(v);
		edge[v].pb(u);
	}
	for (int i = 1; i <= n; ++i) if (dfs(i, 0)) printf("%d ", i);
	return 0;
}

　　

转载于:https://www.cnblogs.com/AnzheWang/p/9643564.html

最后

以上就是搞怪小土豆为你收集整理的AtCoder Grand Contest 010 题解的全部内容，希望文章能够帮你解决AtCoder Grand Contest 010 题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(64)

相关文章

Atcoder Grand Contest 010 D Decrementing
Atcoder Grand Contest 010 D Decrementing
[agc010d] Decrementing - 博弈 结论题 -
[agc010d] Decrementing - 博弈 结论题 -
AtCoder Grand Contest 010AtCoder Grand Contest 010
AtCoder Grand Contest 010AtCoder Grand Contest 010
[AtCoderContest010D]Decrementing
[AtCoderContest010D]Decrementing
AtCoder Grand Contest 010 题解
AtCoder Grand Contest 010 题解
AGC 010D.Decrementing(博弈)
AGC 010D.Decrementing(博弈)
一个人的博弈
一个人的博弈
【CF878E】Numbers on the blackboard 并查集【CF878E】Numbers on the blackboard
【CF878E】Numbers on the blackboard 并查集【CF878E】Numbers on the blackboard

评论列表共有 0 条评论

立即
投稿
返回
顶部