[POJ1082&POJ2348&POJ1067&POJ2505&POJ1960]简单博弈题总结

　　鉴于时间紧张...虽然知道博弈是个大课题但是花一个上午时间已经极限了...

　　希望省选过后再回过头来好好总结一遍吧。

　　接下来为了看着顺眼一点...还是按照难度顺序吧

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.

巴特西

[POJ1082&POJ2348&POJ1067&POJ2505&POJ1960]简单博弈题总结

最新文章

热门文章