【bzoj1457】棋盘游戏

  • 本文为博主原创,未经许可不得转载

题解

这个问题与我们之前遇到的并不类似。我们擅长的问题通常是“不能操作者判负”的问题。因此,我们尝试转化。

注意到,如果初始情况下,有皇后可以通过一步操作直接到达,那么先手只要这么操作,就能直接获胜,因此这种局面是先手必胜的。

否则,玩家除非走投无路,否则一定不能把皇后移动到这些“通过一步操作可以直接到达”的位置(下面简称“禁区”)。也就是说,如果认为这些禁区是不能停留的,那么原问题就转化为了不能操作者判负的问题。

经过这样的转化,模型就不难建出了,这是一个有向无环图,直接按定义计算出每个位置的SG函数值并计算答案即可。

——题解来自王队长《OI中的博弈论》

参考代码

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
#include<bits/stdc++.h>
#define FILE "read"
using namespace std;
const int MAXN=(int)1e3,D=50;
int a[MAXN+D],b[MAXN+D],check[MAXN+D],sg[105][105];
namespace INIT{
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read(){
int x=0,f=1; char ch=getc();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getc();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getc();}
return x*f;
}
}using namespace INIT;
void pre(){
for(int i=0;i<=99;++i) for(int j=0;j<=99;++j){
if(i==j||i*j==0) continue;
memset(check,0,sizeof(check));
for(int k=1;k<min(i,j);++k)check[sg[i-k][j-k]]=1;
for(int k=1;k<i;++k)if(i-k!=j)check[sg[i-k][j]]=1;
for(int k=1;k<j;++k)if(i!=j-k)check[sg[i][j-k]]=1;
for(int k=0;k<=MAXN;++k)if(!check[k]){sg[i][j]=k;break;}
}
}
void solve(){
int n=read(),ans(0);
for(int i=1;i<=n;++i) a[i]=read(),b[i]=read();
for(int i=1;i<=n;++i) ans^=sg[a[i]][b[i]];
puts(ans?"^o^":"T_T");
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
pre();
for(int T=read();T;--T) solve();
return 0;
}
文章目录
  1. 1. 题解
  2. 2. 参考代码
,