鉴于时间紧张...虽然知道博弈是个大课题但是花一个上午时间已经极限了...
希望省选过后再回过头来好好总结一遍吧。
接下来为了看着顺眼一点...还是按照难度顺序吧
POJ1082
一道最简单的博弈题，只需要DP就可以过。
在这道题里我尽情展示了多函数多过程的代码风格。。
program poj1082;
const u:set of ..=[,,,,,,];
var n,i,x,y,z:longint;
f:array[..,..,..]of boolean; function leap(x:longint):boolean;
begin
if x mod = then
begin
if x mod = then exit(true);
end else
begin
if x mod = then exit(true);
end;
exit(false);
end; function exist(x,y,z:longint):boolean;
begin
if y in u then
begin
if z< then exit(true);
end else
begin
if y<> then
begin
if z> then exit(false) else exit(true);
end else
begin
if (z<)or(leap(x)and(z=)) then exit(true);
end;
end;
exit(false);
end; function next_day(x,y,z:longint):boolean;
begin
inc(z);
if not exist(x,y,z) then
begin
inc(y);z:=;
end;
if y> then
begin
inc(x);y:=;
end;
exit(f[x,y,z]);
end; function next_month(x,y,z:longint):boolean;
begin
inc(y);
if y> then
begin
inc(x);y:=;
end;
if not exist(x,y,z) then exit(false);
exit(f[x,y,z]);
end; procedure solve;
var i,j,k:longint;
flag:boolean;
begin
fillchar(f,sizeof(f),false);
for i:= downto do
for j:= downto do
for k:= downto do if exist(i,j,k) then
begin
flag:=true;
if next_day(i,j,k) then flag:=false;
if next_month(i,j,k) then flag:=false;
f[i,j,k]:=flag;
end;
end; begin
assign(input,'poj1082.in');reset(input);
readln(n);
solve;
for i:= to n do
begin
readln(x,y,z);
if f[x,y,z] then writeln('NO') else writeln('YES');
end;
end.
POJ2960
简单的SG函数的运用。
program poj2960;
const maxn=;maxm=;
var sizes,i,n,m,x,ans,j:longint;
s:array[-..maxm]of longint;
w:array[-..maxn]of longint;
vis:array[-..*maxn,-..maxm]of boolean; procedure calc_SG;
var i,j:longint;
begin
fillchar(vis,sizeof(vis),false);
for i:= to maxn do
begin
for j:= to maxm do if not vis[i,j] then break;
w[i]:=j;
for j:= to sizes do vis[i+s[j],w[i]]:=true;
end;
end; begin
//assign(input,'poj2960.in');reset(input);
//assign(output,'poj2960.out');rewrite(output);
read(sizes);
while sizes<> do
begin
for i:= to sizes do read(s[i]);readln;
calc_SG;
readln(m);
for i:= to m do
begin
ans:=;
read(n);
for j:= to n do
begin
read(x);
ans:=ans xor w[x];
end;
if ans> then write('W') else write('L');
readln;
end;
writeln;
read(sizes);
end;
end.
POJ2505
题面很亲切，就是不停乘上2~9之间的一个数，超过了某个数n即算赢。
依稀记得去年暑假做过这道题，当时应该数据比较弱是直接DP过的...
然后先还是无脑DP，然后输出发现了很神奇的规律...
2~9 先手赢
10~18 后手赢
19~162 先手赢
163~324 后手赢
...
想来其实也并无道理，但是找规律无疑是最快捷的方法了。
program poj2505;
var x:int64; function solve(x:int64):boolean;
var k:int64;
begin
k:=;
while true do
begin
k:=k*;
if x<=k then exit(true);
k:=k*;
if x<=k then exit(false);
end;
end; begin
while not eof do
begin
readln(x);
if solve(x) then writeln('Stan wins.') else writeln('Ollie wins.');
end;
end.
POJ2348
这道题我的思考出现了一点问题...
刚开始认为，对于每一个(x,y)到(y,x mod y)的过程，都可以看做是一场Nim游戏
然后石子的个数就是x div y的个数
自己觉得非常有道理，然后就SG敲起来了...
发现怎么都过不去，和标算对拍了之后发现是这样的...
Nim游戏你可以任意选一堆石子开始，而这道题是从大减到小
也就是强制必须先从第一堆石子里取完才能从第二堆取
于是就不可以用SG函数了
继续看，发现如果当x div y=1的时候，只有一种选择
而当x div y>=2的时候，起码有两种选择而且显然是可以交换和对手的身份的
这种情况下就是必胜的。
然后辗转相除套一个特判就可以AC啦
program poj2348;
var tem,x,y:int64; function solve(x,y:int64):boolean;
begin
if y= then exit(false);
if x div y>= then exit(true);
exit(not solve(y,x mod y));
end; begin
assign(input,'poj2348.in');reset(input);
readln(x,y);
while (x<>)or(y<>) do
begin
if x<y then
begin
tem:=x;x:=y;y:=tem;
end;
if solve(x,y) then writeln('Stan wins')
else writeln('Ollie wins');
readln(x,y);
end;
end.
POJ1067
一道裸的威佐夫博弈...
两堆石子中可以在任意一堆中取若干个，也可以在两堆中取相同数量个。
奇异状态(x,y)满足：
x=a[i],y=a[i]+i
而a[i]=i*(sqrt(5)-1)/2+i;
非奇异状态为必胜状态，反之必败。
我是用二分来实现x=a[i]这一步的查找的...
（刚开始非常sx的用了1.618后来发现x<=10^9，乘到后面显然精度不够，然后copy来了一堆长的黄金分割数，但是忘记把小数点前改1了...然后一直WA。发现其实就是(sqrt(5)-1)/2...既简单不用背有精确度高...真是初三内容都还给李老师了...连黄金分割都忘掉了QAQ）
program poj1067;
const INF=;
num=(sqrt()-)/+;
var x,y,tem:int64; function find(x:int64):int64;
var L,R,mid,tem:int64;
begin
L:=;R:=INF;
while L<=R do
begin
mid:=(L+R) >> ;
tem:=trunc(num*mid);
if x=tem then exit(mid);
if x<tem then R:=mid- else L:=mid+;
end;
exit(-);
end; begin
while not eof do
begin
readln(x,y);
if x>y then
begin
tem:=x;x:=y;y:=tem;
end;
tem:=find(x);
if (tem=-)or(tem+x<>y) then writeln() else writeln();
end;
end.