欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

Codefroces 1033C. Permutation Game

程序员文章站 2022-06-16 10:21:50
C. Permutation Game题意:一个线性的棋盘,上面有n个格子编号为1-n,当棋子所在位置满足以下情况时,可以移动1.新格子的数值必须严格大于旧格子2.移动的距离必须是旧格子中数字的整数倍谁不能采取行动,谁就输了,即当前棋子位于一个不能移动的位置求哪些出发格子可以使Alice必胜思路记录每个点下一步能到达的点,建反图然后拓扑如果一个点标记为0代表必输点,为1代表必赢点,-1表示还没判断对每一个入度为0的点,即没有可到达的下一个点的点进行判断如果点u是必输点,说明无法进行下一...

C. Permutation Game

题意:

一个线性的棋盘,上面有n个格子编号为1-n,当棋子所在位置满足以下情况时,可以移动
1.新格子的数值必须严格大于旧格子
2.移动的距离必须是旧格子中数字的整数倍
谁不能采取行动,谁就输了,即当前棋子位于一个不能移动的位置
求哪些出发格子可以使Alice必胜

思路

记录每个点下一步能到达的点,建反图然后拓扑
如果一个点标记为0代表必输点,为1代表必赢点,-1表示还没判断
对每一个入度为0的点,即没有可到达的下一个点的点进行判断

如果点u是必输点,说明无法进行下一步操作,所以,能到达这一点的点一定是必赢点,因为从必赢点跳到这一点,对手就无法进行下一步操作了。

如果点u是必赢点,那么u能到达的点一定至少有一个必输点。如果u的状态已经判断过,那就没有必要在判断,如果是-1 就设置为0

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl &#39;\n&#39;

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int a[maxn], degree[maxn], vis[maxn];
int q[maxn];
vector<int>v[maxn];
int main() {
	int n;cin >> n;
	for (int i = 1;i <= n;++i)cin >> a[i];
	for (int i = 1;i <= n;++i) {
		for (int j = i;j <= n;j += a[i]) {
			if (a[j] > a[i]) {
				v[j].push_back(i);
				degree[i]++;
			}
		}
		for (int j = i;j >= 1;j -= a[i]) {
			if (a[j] > a[i]) {
				v[j].push_back(i);
				degree[i]++;
			}
		}
	}
	memset(vis, -1, sizeof(vis));
	queue<int>que;
	for (int i = 1;i <= n;++i) {
		if (!degree[i])que.push(i), vis[i] = 0;
	}
	while (!que.empty()) {
		int now = que.front();
		que.pop();
		for (int i = 0;i < v[now].size();++i) {
			int t = v[now][i];
			if (vis[now] == 0) {
				vis[t] = 1;
			}
			else if (vis[now] == 1) {
				if (vis[t] == -1)vis[t] = 0;
			}
			degree[t]--;
			if (!degree[t])que.push(t);
		}
	}
	for (int i = 1;i <= n;++i) {
		if (vis[i] == 1)printf("A");
		else printf("B");
	}
	return 0;
}

本文地址:https://blog.csdn.net/zzq0523/article/details/107327899