bzoj1434 [ZJOI2009]染色游戏

Description

一共n × m 个硬币,摆成n × m 的长方形。dongdong 和xixi 玩一个游戏, 每次可以选择一个连通块,并把其中的硬币全部翻转,但是需要满足存在一个 硬币属于这个连通块并且所有其他硬币都在它的左上方(可以正左方也可以正 上方),并且这个硬币是从反面向上翻成正面向上。dongdong 和xixi 轮流操作。 如果某一方无法操作,那么他(她) 就输了。dongdong 先进行第一步操作,假 设双方都采用最优策略。问dongdong 是否有必胜策略。

Input

第一行一个数T,表示他们一共玩T 局游戏。接下来是T 组游戏描述。每 组游戏第一行两个数n;m,接下来n 行每行m 个字符,第i 行第j 个字符如 果是“H” 表示第i 行第j 列的硬币是正面向上,否则是反面向上。第i 行j 列 的左上方是指行不超过i 并且列不超过j 的区域。

Output

对于每局游戏,输出一行。如果dongdong 存在必胜策略则输出“- -”(不含 引号) 否则输出“= =”(不含引号)。(注意输出的都是半角符号,即三个符号 ASCII 码分别为45,61,95)

Sample Input

32
3
HHH
HHH
2 3
HHH
TTH
2 1
T
H

Sample Output

= =
- -
- -

HINT

对于40% 的数据,满足1 ≤ n;m ≤ 5。
对于100% 的数据,满足1 ≤ n;m ≤ 100,1 ≤ T ≤ 50。

正解:$SG$函数。

又是这种硬币问题。。我开始以为每次翻转一个矩形,然后写了个$dp$求$SG$函数并成功爆零。。

然后写一个搜索可以发现,如果$i=1$或$j=1$,$SG[i][j]=lb(max(i,j))$,否则$SG[i][j]=2^{i+j-2}$。

但是太大了,所以我们只记录二进制的每一位是否为$0$就行了。

 #include <bits/stdc++.h>
#define il inline
#define RG register
#define ll long long
#define lb(x) (x & -x) using namespace std; int cnt[],bin[],n,m,ans; il int gi(){
RG int x=,q=; RG char ch=getchar();
while ((ch<'' || ch>'') && ch!='-') ch=getchar();
if (ch=='-') q=-,ch=getchar();
while (ch>='' && ch<='') x=x*+ch-,ch=getchar();
return q*x;
} il char gc(){
RG char ch=getchar();
while (ch!='H' && ch!='T') ch=getchar(); return ch;
} il void get(RG int x,RG int y){
if (x==){ cnt[bin[lb(y)]]^=; return; }
if (y==){ cnt[bin[lb(x)]]^=; return; }
cnt[x+y-]^=; return;
} il void work(){
n=gi(),m=gi(),memset(cnt,,sizeof(cnt));
for (RG int i=;i<=n;++i)
for (RG int j=;j<=m;++j)
if (gc()=='T') get(i,j);
for (RG int i=;i<=;++i)
if (cnt[i]){ puts("-_-"); return; }
puts("=_="); return;
} int main(){
#ifndef ONLINE_JUDGE
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
#endif
for (RG int i=;i<=;++i) bin[i]=bin[i>>]+;
RG int T=gi(); while (T--) work(); return ;
}
上一篇:JVM逃逸分析


下一篇:【BZOJ1434】[ZJOI2009]染色游戏(博弈论)