Vođe

[COCI 2017/2018 #4] Vođe

Details

题目描述

众所周知，山羊和绵羊为了它们放牧的田地已经争斗多年。在经历了许多激烈的战斗后，山羊首领和绵羊首领决定会面，尝试为他们的问题找到一个和平的解决方案。经过多小时的讨论，他们同意为每块田地玩一个游戏，胜者将获得在该田地放牧的权利。

游戏的规则是，总共有 $N$ 只动物（可能是山羊或绵羊）围成一个圈（山羊和绵羊的具体顺序由它们的首领协商决定）。在动物 $i$（$1\le i\le N-1$）之后，游戏由动物 $i+1$ 继续，而在动物 $N$ 之后，游戏由动物 $1$ 继续。开始游戏的动物可以从区间 $[1,K]$ 中说出任意一个正整数，但这个数字不能大于 $M$。如果开始游戏的动物说了数字 $j$，那么下一个动物可以在区间 $[j+1,j+K]$ 中说一个数字，但这个数字也不能大于 $M$。换句话说，每只动物可以说出比前一只动物所说的数字大至少 $1$、最多 $K$ 的数字，但新数字不能大于 $M$。如果一只动物必须说出数字 $M$，它所在的队伍（山羊或绵羊）就会输掉。

如果山羊和绵羊都以最佳策略进行游戏，对于每个 $i$（$1\le i\le N$），确定如果游戏由第 $i$ 只动物开始，谁将赢得这块田地。

输入格式

输入的第一行包含 $N$、$M$ 和 $K$（$1\le N,M,K\le 5000$），如题目所述。接下来的行包含 $N$ 个数字，如果第 $i$ 只动物是绵羊，则为 0，如果是山羊，则为 1。

输出格式

输出 $N$ 个以空格分隔的数字。对于每只动物 $i$（$1\le i\le N$），如果游戏由第 $i$ 只动物开始时绵羊将赢得田地，则输出 0，否则则输出 1。

输入输出样例 #1

输入 #1

2 9 2
0 1

输出 #1

0 1

输入输出样例 #2

输入 #2

6 499 5
1 0 0 1 1 0

输出 #2

0 1 1 1 1 0

输入输出样例 #3

输入 #3

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

输出 #3

1 1 1 1 1 1 1 1 1 1

说明/提示

在总分值为 $60\%$ 的测试用例中，将满足 $1\le N,M,K\le 500$。

第一个样例的说明：

当绵羊先开始时，它可以这样进行游戏：

绵羊以数字 2 开始，之后山羊可以说 3 或 4。在这两种情况下，绵羊可以说 5，之后山羊可以说 6 或 7。在这两种情况下，绵羊可以说 8，之后山羊别无选择只能说 9，从而输掉游戏和田地。

题面翻译由 ChatGPT-4o 提供，123asdf123 修缮。

---

分析

原来这不是博弈论啊，就是一个$DP$啊

对于第$i$只羊，如果后面$k$只羊都不是自己的同类，那么此时我们的状态就需要转换，如果是必败态，那么就转化为必胜态，否则反之

所以直接$DP$可以写出一个$O(nmk)$的代码，将$O(k)$遍历转化成前缀和$O(1)$就可以了

时间复杂度：$O(nm)$

---

AC代码

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair< int,int >
#define QWQ return 0;
#define QAQ return 

const int N=5e3+10;

int sum[N][N];
bool goat[N];
bool f[N][N];

int main()
{
    // freopen( "1.in","r",stdin );
    // freopen( "1.out","w",stdout );
    ios::sync_with_stdio( false );
    cin.tie( nullptr ); cout.tie( nullptr );
    int n, m, k;
    cin>>n>>m>>k;
    for( int i=1;i<=n;i++ )
        cin>>goat[i],
        sum[i][1]=f[i][1]=( goat[i]^1 );
    for( int j=2;j<=m;j++ ) for( int i=1;i<=n;i++ )
    {
        if( sum[( i+1 > n ? 1 : i+1 )][j-1]-sum[( i+1 > n ? 1 : i+1 )][max( 0,j-k-1 )] ==
        ( ( goat[i]^1 )*min( j-1,k ) ) ) f[i][j]=( goat[i]^1 );
        else                             f[i][j]=goat[i];
        sum[i][j]=sum[i][j-1]+f[i][j];
    }
    for( int i=1;i<=n;i++ ) cout<<f[i][m]<<" ";
	QWQ
}