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 '\n' 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; }
