(COCI 2017/2018 4) Vođe

题解

题意

有 N 只动物围成一圈，编号为 1 到 N。每只动物属于绵羊（0）或山羊（1）。游戏从某一动物开始，顺时针依次轮流进行（N 之后回到 1）。

游戏规则：

• 起始动物可以从 1 到 K 中选择一个正整数作为初始数字，但不能超过 M。
• 之后的每只动物必须说出比前一个数字大 至少 1、至多 K 的数字，且新数字不能超过 M。
• 若某只动物被迫说出数字 M（即上家说了 M-K 到 M-1 之间的数，且唯一合法选择是 M），则该动物所在的队伍输掉游戏。

双方（山羊和绵羊）都采取最优策略。对于每只动物 i（1 ≤ i ≤ N），判断如果游戏由第 i 只动物开始，最终哪一方会获胜。

输出格式：输出 N 个数，第 i 个数为 0 表示绵羊获胜，为 1 表示山羊获胜。

数据范围

• 1 ≤ N, M, K ≤ 5000
• 对于 60% 的数据：1 ≤ N, M, K ≤ 500

解法

这是一道十分经典的博弈论问题。

首先我们把报数看作取石子，题意转换为$M$个石子，从$i$开始取，每次至少取$1$个，最多取$K$个问最后那个阵营获胜。

对于单独的一只动物而言，他的决策只有$K$种，并且决策的胜负只与石子的个数有关。

我们设计状态$f_{i,j}$表示对于第$i$只动物来说，当前有$j$颗石子是必胜局面还是必败局面。

转移显然是由后面的动物反推回来，如果说$\sum_{p=1}^{k}f_{i+1,j-p}=0$并且后面的动物与这个动物阵营相同，那么对于这个动物来说无论如何决策都会面临必败局面，所以对于这个动物来说也是必败的。而如果结果$>0$就说明存在一个决策可以面临必胜局面，那么对于这个动物来说这就是必胜的。

反之如果后面的动物与这个动物阵营不同，那么$\sum_{p=1}^kf_{i+1,j-p}=k$就说明无论如何决策，下一个动物都是必胜的，那么对这个不同阵营的动物来说这个局面就是必败的，如果$<k$那就存在一种决策让对方必败，那对这个动物来说就是必胜的。

$dp$时这个$\sum$可以通过前缀和处理，那么时间复杂度就是$O(nm)$

代码

code

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
int n,m,k;
int a[N];
int f[N][N];
int sum[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[j]==a[j%n+1]) 
            {
                if(sum[i][j%n+1]-sum[max(i-k,0)][j%n+1]>0) f[i][j]=1;
                else f[i][j]=0;
            }
            else
            {
                if(sum[i][j%n+1]-sum[max(i-k,0)][j%n+1]<k) f[i][j]=1;
                else f[i][j]=0;
            }
            sum[i+1][j]=sum[i][j]+f[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(f[m-1][i]) cout<<a[i]<<' ';
        else cout<<(a[i]^1)<<' ';
    }
    return 0;
}