2016多校联合训练1 B题Chess (博弈论 SG函数)
2024-08-27 16:20:35
题目大意:一个n(n<=1000)行,20列的棋盘上有一些棋子,两个人下棋,每回合可以把任意一个棋子向右移动到这一行的离这个棋子最近的空格上(注意这里不一定是移动最后一个棋子),不能移动到棋盘外,不能移动了就算输,两个人都用最优策略,问先手是否有必胜策略。
这题显然就是SG函数了吧。行与行之间互不影响,所以可以看成n个子游戏,求出它们各自的SG函数然后异或一下就可以了。我们发现只有20列,2^21=2097152,所以我们可以先把行的所有情况的SG函数预处理出来,然后每次询问O(1)就行了。
代码如下:
var
t,i,j,m,v,c,res,n,cl:longint;
cnt:array[..]of longint;
a:array[..]of longint; procedure calc(x,c:longint);
begin
dec(x,<<(c-));inc(c);
while c<= do
begin
if x and (<<(c-))= then break;
inc(c);
end;
if c> then exit;
inc(x,<<(c-));
cnt[a[x]]:=;
end; procedure init;
begin
for i:=(<<)- downto do
begin
fillchar(cnt,sizeof(cnt),);
for j:= to do
if i and (<<(j-))<> then calc(i,j);
for j:= to do
if cnt[j]= then
begin
a[i]:=j;
break;
end;
end;
end; procedure solve;
begin
readln(n);res:=;
for i:= to n do
begin
c:=;
read(m);
for j:= to m do
begin
read(v);
c:=c or(<<(v-));
end;
res:=res xor a[c];
end;
if res<> then writeln('YES')
else writeln('NO');
end; begin
init;
readln(t);
while t> do
begin
dec(t);
solve;
end;
end.
最新文章
- Windows操作系统组策略应用全攻略
- StormNimbus集群保证CAP流程
- Java上面出现这个错误如何解决关于XML的
- iOS—网络实用技术OC篇&;网络爬虫-使用java语言抓取网络数据
- ACCP7.0-S2-复习自测-15测试分析
- linux redhat6.4安装oracle11g
- hdu 2874 Connections between cities [LCA] (lca->;rmq)
- 水题 Codeforces Round #296 (Div. 2) A. Playing with Paper
- uTenux-OS-Task再探
- Android图表
- [原博客] POJ 2425 A Chess Game
- Angular 2 npm start 报错
- app被Rejected 的各种原因翻译。这个绝对有用。
- Android采取async框架文件上传
- HHVM Installation and Configuration(HHVM 安装及配置)
- C#下丢掉.asmx文件的WebService的实现
- Oracle函数之chr
- 理解javascript模块化(转)
- 238. Product of Array Except Self除自身以外数组的乘积
- nodejs+express安装配置(Linux版本)