C. Game Master

C. Game Master

本题可以抽象为图论问题:

由题意可知,在两张地图上权值最大的那两个人xy能赢,那么能赢这两个人的也能赢,依次类推,我们根据玩家在两张地图上的权值对玩家的下标进行建图,strength小的玩家A指向strength刚刚大于AB,形成了一棵树,我们对xy进行\(dfs\),能被指向的玩家可以成为赢家。

代码:

#include <bits/stdc++.h>
#define pb push_back
#define LL long long
#define sz(x) (int)x.size()
#define all(s) (s).begin(), (s).end()
using namespace std;

const int N = 200010;
struct athlete{
	int x;
	int y;
	int index;
}a[N];

int n;
int h[N], ne[N], idx, e[N], ans[N], st[N];

bool cmp1(athlete A, athlete B){
	return A.x < B.x;
}

bool cmp2(athlete A, athlete B){
	return A.y < B.y;
}

void add(int a, int b){
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++; 
}

void dfs(int x){
	st[x] = true;
	ans[x] = 1;
	for(int i = h[x]; i != -1; i = ne[i]){
		int y = e[i];
		if(!st[y]) dfs(y);
	}
}

void solve()
{
	scanf("%d",&n);
	idx = 0;
	for(int i = 1; i <= n; i ++ ){
		h[i] = -1;
		ans[i] = 0;
		st[i] = false;
	}
	for(int i = 1; i <= n; i ++ ) scanf("%d",&a[i].x);
	for(int i = 1; i <= n; i ++ ){
		scanf("%d",&a[i].y);
		a[i].index = i;	
	}
	sort(a + 1, a + 1 + n, cmp1);
	for(int i = 2; i <= n; i ++ ) add(a[i - 1].index, a[i].index);
	int xx = a[n].index;
	sort(a + 1, a + 1 + n, cmp2);
	for(int i = 2; i <= n; i ++ ) add(a[i - 1].index, a[i].index);
	dfs(a[n].index);
	for(int i = 1; i <= n; i ++ ) st[i] = false;
	dfs(xx);
	for(int i = 1; i <= n; i ++ ) printf("%d",ans[i]);
	printf("\n");
}

int main()
{
	int test;
	scanf("%d", &test);
	while(test -- )
	{
		solve();
	}
	return 0;
}
上一篇:【C语言小游戏】扫雷


下一篇:CF 1608C - Game Master