Codeforces1033C 博弈

Posted on | In , ,

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

题目链接

题解

  • 显然O(nlogn)可以预处理出所有点可以到达的点。
  • 考虑博弈中必胜态和必败态的定义。
  • 必胜态：必胜态的后继状态中存在至少一个必败态(这样处于必胜态，走一步到达必败态使得对手处于必败态)。
  • 必败态：必败态的后继状态全是必胜态。
  • 要从小到大枚举初始的必败态，否则有些状态处理不到

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;

int n, a[maxn], sg[maxn];
vector<int>g[maxn];
int d[maxn];


int main()
{

    scanf("%d", &n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d", &a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=a[i]+i;j<=n;j+=a[i])
        {
            if(a[j]>a[i]){
                g[j].push_back(i);
                d[i]++;
            }
        }
        for(int j=i-a[i];j>=1;j-=a[i])
        {
            if(a[j]>a[i]){
                g[j].push_back(i);
                d[i]++;
            }
        }
    }
    memset(sg, -1, sizeof(sg));
    stack<int>q;
    for(int i=1;i<=n;i++)
    {
        if(!d[i]) {
            q.push(i);
            sg[i]=0;
        }
    }
    while(!q.empty())
    {
        int u=q.top();
        q.pop();
        for(int i=0;i<int(g[u].size());i++)
        {
            int v=g[u][i];
            if(sg[v]==-1){
                if(sg[u]==0)
                {
                    sg[v]=1;
                }
                else
                     sg[v]=0;
            }
            else
            {
                if(sg[u]==0)
                    sg[v]=1;
            }
            d[v]--;
            if(!d[v])
                q.push(v);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(sg[i])putchar('A');
        else putchar('B');
    }
}