Problem - C - Codeforces
经过漫长的一天， Aice和Bob决定玩一个小游戏。游戏棋盘由n个格子组成，在一条直线上，编号从1到n,每个格子包含一个数字4;,qy在1到n.之间，而且没有两个格子包含相同的数字。
一个棋子被放在其中一个格子里。他们轮流移动棋子，先是Alice。当前的玩家只能在满足以下两个条件的情况下从格子i移动到格子j:
新格子j中的数字必须严格大于旧格子i中的数字(即aj > ai)。
棋子在这次移动中走过的距离必须是旧格子中的数字的倍数(即|i-j mod a; = 0)。
谁不能移动了，谁就输了。对于每个可能的初始位置，确定如果他们都采取最优策略，谁将获胜。可以证明，游戏总是有限的，即总有一方有必胜策略。
输入∶
第一行包含一个整数n(1≤n≤105)——数字的数量。
第二行包含n个整数a1, @2 .. . ,n (1<a <n)。此外，不存在不同的下标i,j使得;=@jo
输出:
输出一个长度为n的宇符串s，其中第i个字符表示如果棋子最初放在第i个格子中，则游戏的结果如何。如果Alice获胜，则s;等于"A"，否则s;等于"B8"。
Examples
input
Copy
8 3 6 5 4 2 7 1 8
output
Copy
BAAAABAB
input
Copy
15 3 11 2 5 10 9 7 13 15 8 4 12 6 1 14
output
Copy
ABAAAABBBAABAAB
在第一个示例中，如果Bob将代币放在数字上（而非位置）：
- Alice可以移动到任何数字。她可以通过选择7获胜，而Bob没有可行的移动。
- Alice可以移动到3和5。当移动到5时，Bob可以通过移动到8赢得胜利。如果她选择3，则获胜，因为Bob只能移动到4，而此时Alice可以移动到8。
- Alice只能移动到4，此后Bob通过移动到8获胜。 4、5或6：Alice通过移动到8获胜。 7或8：Alice无法移动，因此立即输掉比赛。
题解:
必败态的上一个肯定是必胜态,而题目有规定了,只能从小数到大数,开始走,
我们从大到小开始枚举,
比如大小为n的,肯定先手拿必败,接着我们根据拓扑排序的思想,看当前位置的上一个是否是必败态,如果是说明此时就是必胜态,
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int,int> PII;
int mod = 1e9 + 7;
int pos[200050];
int a[200050];
int ans[200050];
void solve()
{
int n;
cin >> n;
for(int i = 1;i <= n;i++)
{
int x;
cin >> x;
pos[x] = i;
a[i] = x;
}
for(int i = n;i >= 1;i--)
{
int u = pos[i];
int v = u;
ans[u] = 0;
while(v - a[u] > 0)
{
v -= a[u];
}
for(;v <= n;v += a[u])
{
if(a[v] > a[u]&&ans[v] == 0)
{
ans[u] = 1;
break;
}
}
}
for(int i = 1;i <= n;i++)
{
if(ans[i])
cout <<"A";
else
cout <<"B";
}
}
signed main()
{
// ios::sync_with_stdio(0 );
// cin.tie(0);cout.tie(0);
int t = 1;
// cin >> t;
while(t--)
{
solve();
}
}
