YbtOJ 986「博弈论」格子染色

(Updated: )
oi
,

题目链接：YbtOJ #986

小 A 和小 B 有一张包含 $n$ 个格子的格子纸条。

总共有 $k$ 种颜色，编号为 $1\sim k$。初始有一些格子已经染上了颜色（保证初始相邻格子颜色不同）。

小 A 和小 B 对于这张纸条很感兴趣，他们决定利用这张纸条玩一个游戏：

  • 小 A 先手，小 B 后手，两人轮流操作。
  • 轮到一个人操作时，他需要选择一个未被染色的格子，给它染上一种颜色，要求相邻格子不能被染上相同的颜色。
  • 率先无法进行操作的人输了。

现在小 A 希望你帮他判断对于给定的局面，他是否有必胜策略。

$Subtask1(15\%)$：$n\le6$。

$Subtask2(10\%)$：$n\le100$。

$Subtask3(10\%)$：$n\le10^3$。

$Subtask4(10\%)$：所有格子初始都未染色。

$Subtask5(15\%)$：$k=1$。

$Subtask6(15\%)$：$k=2$。

$Subtask7(10\%)$：$k=3$。

$Subtask8(15\%)$：无特殊限制。

对于$100\%$的数据，$1\le n,k\le10^5$

Solution

Part Ⅰ：$k\ge 3$

每个格子必然都能被染上颜色。

因此胜负情况只取决于未被染色的格子数的奇偶性，即当且仅当未被染色的格子数为奇数时先手胜。

Part Ⅱ：$k=1$

设 $sg_n$ 表示有 $n$ 个空格子的博弈 $sg$ 函数。

一种情况是选择边上的格子，后继为 $sg_{n-2}$。

另一种是选择中间某个格子，那么它以及相邻两侧共三个格子都不能再选择，后继状态为 $SG1(i)\oplus SG1(n-3-i)$。

所以有：
$$
sg_n=\texttt{mex}{sg_{n-2},\texttt{mex}{i=0}^{n-3}{sg_i\oplus sg{n-3-i}}}
$$
打表发现有循环节，于是做完了。

Part Ⅲ：$k=2$

对于一个大小为 $S$ 的区间，考虑其在 $k=2$ 时的 $SG$ 函数。

对于两端有限制的情况，发现只有两种可能的终止态：区间两端限制颜色不同，区间大小为 $0$ 或 $1$。此外，发现当区间两端限制颜色相同时一次操作只会产生两个限制颜色都不同或都相同的区间，区间两端限制颜色不同时一次操作会产生一个限制颜色不同的区间和一个限制颜色相同的区间。于是可以猜想此时的 $SG$ 函数只与区间两端限制颜色是否相同有关，进而发现当限制颜色不同时 $SG$ 函数值为 $0$，当限制颜色相同时 $SG$ 函数值为 $1$。

对于一端有限制的情况，归纳可证大小为 $S$ 的区间 $SG$ 值就是 $S$。如果我们选择在第 $i$ 个位置（$1\le i\le S$）填上与限制颜色不同的颜色，那么后继状态是 $(i-1)\oplus 0$，即后继状态包含 $0\sim S-1$；如果我们选择在第 $i$ 个位置（$1\le i < S$）填上与限制颜色相同的颜色，那么后继状态是 $(i-1)\oplus 1$，满足 $(i-1)\oplus1\le i < S$。因此后继状态的 $\texttt{mex}$ 就是 $S$，即 $SG$ 值等于 $S$。

对于没有限制的情况，选择在第 $i$ 个位置上填入一个数的后继状态是 $(i-1)\oplus(n-i)$。显然，只有当 $n$ 是奇数的时候才有可能出现 $(i-1)\oplus(n-i)=0$。又由于没有限制肯定是全局的情况，不需要求出具体的 $SG$ 值，只要判断先手是否必胜即可。

Code

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
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10;
int n,k,a[N],cnt,Ans,vis[305],sg[305],sg2[N];
int main(){
    freopen("color.in","r",stdin),freopen("color.out","w",stdout);
    RI i,j,lst;for(read(n,k),i=1;i<=n;i++) read(a[i]),!a[i]&&++cnt;
    if(k>=3) return puts(cnt&1?"YES":"NO"),0;
    if(k==1){
        for(sg[1]=1,i=2;i<=300;i++){
            memset(vis,0,sizeof(vis));
            vis[sg[i-2]]=1;
            for(j=0;j<=i-3;j++) vis[sg[j]^sg[i-j-3]]=1;
            sg[i]=0;W(vis[sg[i]]) sg[i]++;
        }
        #define GS(x) (sg[(x)>100?((x)-100)%102+100:(x)])
        for(lst=0,i=1;i<=n;i++) if(a[i]) Ans^=GS(max(0,lst?i-lst-3:i-2)),lst=i;
        Ans^=GS(max(0,lst?n-lst-1:n));
        return puts(Ans?"YES":"NO"),0;
    }
    if(cnt==n)  return puts(n&1?"YES":"NO");
    #define SG(l,r) (1<=l&&r<=n?a[l]==a[r]:r-l+1)
    for(lst=0,i=1;i<=n;i++) if(a[i]) Ans^=SG(lst,i),lst=i;
    Ans^=SG(lst,n+1);return puts(Ans?"YES":"NO"),0;
}