JZOJ – 5778 没有硝烟的战争

Time Limit : 3000ms
Memory Limit : 512MB

Description

被污染的灰灰草原上有羊和狼。有 $N$ 只动物围成一圈，每只动物是羊或狼。
该游戏从其中的一只动物开始，报出 $[1,K] $ 区间的整数，若上一只动物报出的数是 $x$ ，下一只动物可以报 $[x+1,x+K]$ 区间的整数，游戏按顺时针方向进行。每只动物报的数字都不能超过 $M$ 。若一只动物报了 $M$ 这个数，它所在的种族就输了。问以第 $i$ 只动物为游戏的开始，最后哪种动物会赢？

Input

第一行输入三个正整数 $N$，$M$，$K$。
接下来一行 $N$ 个正整数，分别表示 $N$ 只动物的种类，以顺时针的方向给出。$0$ 代表羊，$1$代表狼。

Output

一行输出 $N$ 个整数，表示若从第 $i$ 只动物开始，赢的动物的种类。同上，$0$ 代表羊，$1$ 代表狼。

Sample Input

Case 1

2 9 2
0 1

Case 2

6 499 5
1 0 0 1 1 0

Case 3

10 100 10
0 0 0 1 1 1 1 0 1 1

Sample Output

Case 1

0 1

Case 2

0 1 1 1 1 0

Case 3

1 1 1 1 1 1 1 1 1 1

Data Constraint

对于60%的数据，1 <= N, M, K <= 500
对于100%的数据，1 <= N, M, K <= 5000

解题思路

第一次AC博弈论祭

我们用1表示当前状态是必胜态，0表示当前状态是必败态。

设 $f[i][j]$ 表示现在进行到第 $i$ 个生物，已经报到了 $j$

每个物种都期望本种族赢，那么我们考虑转移。

如果当前状态下，下一个生物和当前生物的种族不同，那么下一个生物在可选状态内如果存在一个必败态，那么该生物必胜，反之必败。

如果当前状态下，下一个生物和当前生物的种族相同，那么下一个生物在可选状态内如果存在一个必胜态，那么该生物必胜，反之必败。

特别注意，因为动物们围成了一个圈，所以 $n$ 的下一个生物是 $1$

如果暴力统计下一个生物可选状态内有无必胜态，那么会超时，但是可以通过前缀和来统计。（大于0就存在必胜态，等于0不存在）

最后对于每一个生物 $i$，枚举它可以报出的区间 $[1, k]$，检查有无必胜态即可。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 5000 + 10;

inline int read(){
    int x = 0;
    char ch = getchar();

    while(ch < '0' || ch > '9'){
        ch = getchar();
    }

    while('0' <= ch && ch <= '9'){
        x = x*10 + ch - '0';
        ch = getchar();
    }

    return x;
}

int data[MAXN];
int f[MAXN][MAXN];
int sum[MAXN][MAXN];

int n, m, k;

int main(){

    //freopen("vode.in", "r", stdin);
    //freopen("vode.out", "w", stdout);

    n = read();
    m = read();
    k = read();

    for(register int i=1; i<=n; i++){
        data[i] = read();
    }

    for(register int j=m-1; j>=1; j--){
        for(register int i=1; i<=n; i++){
            int next = (i % n) + 1;

            if(data[i] == data[next]){
                //similar to next

                if(sum[next][j+1] - sum[next][min(m, j+k)+1] > 0)
                    f[i][j] = 1;
                else
                    f[i][j] = 0;
            }else{
                if(sum[next][j+1] - sum[next][min(m, j+k)+1] == 0)
                    f[i][j] = 1;
                else
                    f[i][j] = 0;
            }

            sum[i][j] = sum[i][j+1] + f[i][j];
        }
    }

    for(register int i=1; i<=n; i++){
        bool flag = true;

        for(register int j=1; j<=k; j++){
            if(f[i][j]){
                flag = false;
                break;
            }
        }

        if(flag)
            data[i] = !data[i];

        printf("%d ", data[i]); 
    }
}