CF 1033 C. Permutation Game

C. Permutation Game

http://codeforces.com/contest/1033/problem/C

题意：

　　一个排列，每个位置i走到的位置j满足：a[j]>a[i]，(j-i)是a[i]的倍数。问从每个位置开始，是否有必胜策略。

分析：

　　博弈论+拓扑。

　　由于是一个排列，那么可以枚举每个数，判断这个位置的a是否大于它，如果可以连边。这样的复杂度是$nlogn$的。

　　然后对于一些无路可走的点，这是必败态，根据必胜和必败的定义：必胜态的后继状态中存在至少一个必败态，必败态的后继状态全是必胜态。

　　然后建反图，在DAG上拓扑。

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<cctype>

 #include<set>

 #include<vector>

 #include<queue>

 #include<map>

 #define fi(s) freopen(s,"r",stdin);

 #define fo(s) freopen(s,"w",stdout);

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 int a[N], deg[N], q[N], f[N];

 vector<int>T[N];

 int main() {

     int n = read();

     for (int i=; i<=n; ++i) a[i] = read();

     for (int i=; i<=n; ++i) {

         for (int j=i+a[i]; j<=n; j+=a[i])

             if (a[j] > a[i]) T[j].push_back(i), deg[i] ++;

         for (int j=i-a[i]; j>=; j-=a[i])

             if (a[j] > a[i]) T[j].push_back(i), deg[i] ++;

     }

     int L = , R = ;

     memset(f, -, sizeof(f));

     for (int i=; i<=n; ++i)

         if (!deg[i]) q[++R] = i, f[i] = ;

     while (L <= R) {

         int u = q[L ++];

         for (int sz=T[u].size(),i=; i<sz; ++i) {

             int v = T[u][i];

             if (f[v] == -) {

                 if (f[u] == ) f[v] = ;

                 else f[v] = ;

             }

             else {

                 if (f[u] == ) f[v] = ;

             }

             deg[v] --;

             if (!deg[v]) q[++R] = v;

         }

     }

     for (int i=; i<=n; ++i) {

         if (f[i]) putchar('A');

         else putchar('B');

     }

     return ;

 }