博弈论

2014.1.26开坑

听蔡大神讲了好多。

//不定时不定期填坑

=======================================================================================

无聊的定义

｛//用括号注释（无视）掉

P位置和N位置(先手必败状态和先手必胜状态)
我们会发现对于N位置和P位置有一些性质，这些性质的前提是，这是公平游戏，且有终点。
(1) 终点是P位置。
(2) 所有P位置能转移到的都是N位置
(3) N位置至少能转移到一个P位置
（也就是轮到你走时无论怎么走都输，那你就输定了，那么你就是p位置。如果轮到你走时你可以走一步让别人接下来无论怎么走都输，那你就是N位置。）

3.Nim和
首先，我们定义nim和为两个数或多个数在二进制下的异或和(异或和部分不作展开介绍，请不懂的读者自行找资料)。我们定义“⊕”为Nim和的运算符号。例如，如果x与y的Nim和是z，那么我们表示为 x⊕y=z。

波顿定理。
波顿定理：对n堆火柴(x1,x2,x3,...,xn)，若x1⊕x2⊕...⊕xn = 0，则这个状态为P位置，否则为N位置。

sg函数
定义：g(x) = min{n ≥ 0 : n ≠ g(y) | y ∈ F(x)}（F(x)表示x的后继）
不存在于x的所有后继的SG值中的最小值。
比如F(x)=｛1，2，3｝且g(1)=1,g(2)=2,g(3)=3那么g(4)=0
再比如F(x)=｛1，2，3｝且g(1)=0,g(2)=2,g(3)=3那么g(4)=1
如果g(x)=0，显然这是个P位置，如果g(x)≠0，显然这是个N位置。

SG定理
SG定理：母游戏的SG值等于其各个子游戏的SG值的Nim和。

｝

 =================================================================================

 找到的不错的整理

http://blog.csdn.net/acm_cxlove/article/details/7854526

 阶段博弈论

http://blog.csdn.net/kk303/article/details/6692506

题目合集

 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=68459#overview

http://www.cnblogs.com/XDJjy/p/3351946.html?utm_source=tuicool

POJ2960 S-Nim

非递归版

var
  chose:array[0..100]of boolean;
  sg,a:array[0..10000]of longint;
  sum:longint;

procedure into;
var
  i,j:longint;
begin
  for i:=1 to sum do read(a[i]);
  for i:=1 to 10000 do begin
    fillchar(chose,sizeof(chose),false);
    for j:=1 to sum do
      if i>=a[j] then chose[sg[i-a[j]]]:=true;
    j:=0;
    while chose[j] do inc(j);
    sg[i]:=j;
  end;
end;

procedure work;
var
  i,j,k,n,m,ans:longint;
begin
  read(m);
  while m>0 do begin
    dec(m);
    read(n);
    ans:=0;
    for i:=1 to n do begin
      read(j);
      ans:=ans xor sg[j];
    end;
    if ans>0 then write('W')
      else write('L');
  end;
  writeln;
end;

begin
  while true do begin
    read(sum);
    if sum=0 then break;
    into;
    work;
  end;
end.

递归版

var
  sg,a:array[0..10000]of longint;
  sum:longint;


function getsg(x:longint):longint;
var
  i,j:longint;
  chose:array[0..100]of boolean;
begin
  if sg[x]>=0 then exit(sg[x]);
  fillchar(chose,sizeof(chose),false);
  for i:=1 to sum do begin
    j:=x-a[i];
    if j>=0 then
      chose[getsg(j)]:=true;
  end;
  i:=0;
  while chose[i] do inc(i);
  sg[x]:=i;
  exit(i);
end;

procedure work;
var
  i,n,m,ans:longint;
begin
  fillchar(sg,sizeof(sg),255);
  for i:=1 to sum do read(a[i]);
  read(m);
  while m>0 do begin
    dec(m);
    read(n);
    ans:=0;
    while n>0 do begin
      dec(n);
      read(i);
      ans:=ans xor getsg(i);
    end;
    if ans>0 then write('W')
      else write('L');
  end;
  writeln;
end;


begin
  while true do begin
    read(sum);
    if sum=0 then break;
    work;
  end;
end.

速度差不多（非递归快了一点点）

【poj2975】Nim

题解：n堆xor值>0时先手必胜。然后我们再来想一下必胜的情况第一步怎么取，显然就是要让当前局面取完后走入xor值为0的状态，那么很简单，我们就找某一堆是否可以使xor值变成0，显然如果可以的话，比如是ans xor a[i]<=a[i]，这样才存在有且只有一个值（设为d）使a[i]堆取走d个后剩下的所有值xor后为0.

var
  i,j,n,ans,sum:longint;
  a:array[0..1000]of longint;
begin
  while true do begin
    read(n);
    if n=0 then break;
    ans:=0;
    for i:=1 to n do begin
      read(a[i]);
      ans:=ans xor a[i];
    end;
    sum:=0;
    if ans>0 then
      for i:=1 to n do
        if ans xor a[i]<=a[i] then inc(sum);
    writeln(sum);
  end;
  readln;
end.

【poj2425】A Chess Game

直接sg搞定

非递归

type
  arr=record
    toward,from,next1,next2:longint;
  end;
var
  edge:array[0..1000005]of arr;
  first,last,sg,p,num:array[0..1005]of longint;
  chose:array[0..1005]of boolean;
  n,total:longint;


procedure addedge(j,k:longint);
begin
  inc(total);
  edge[total].toward:=k;
  edge[total].from:=j;
  edge[total].next1:=first[k];
  first[k]:=total;
  edge[total].next2:=last[j];
  last[j]:=total;
  inc(num[k]);
end;

procedure atfirst;
var
  head,tail,i,x,too:longint;
begin
  head:=0;
  tail:=0;
  for i:=1 to n do
    if num[i]=0 then begin
      inc(tail);
      p[tail]:=i;
    end;
  while head<tail do begin
    inc(head);
    x:=p[head];

    i:=first[x];
    fillchar(chose,sizeof(chose),false);
    while i>0 do begin
      chose[sg[edge[i].from]]:=true;
      i:=edge[i].next1;
    end;
    i:=0;
    while chose[i] do inc(i);
    sg[x]:=i;

    i:=last[x];
    while i>0 do begin
      too:=edge[i].toward;
      dec(num[too]);
      if num[too]=0 then begin
        inc(tail);
        p[tail]:=too;
      end;
      i:=edge[i].next2;
    end;

  end;
end;

procedure work;
var
  i,ans,m:longint;
begin
  while true do begin
    read(m);
    if m=0 then break;
    ans:=0;
    while m>0 do begin
      dec(m);
      read(i);
      ans:=ans xor sg[i+1];
    end;
    if ans>0 then writeln('WIN')
      else writeln('LOSE');
  end;
end;

procedure into;
var
  i,j,k:longint;
begin
  for i:=1 to n do begin
      read(j);
      while j>0 do begin
        dec(j);
        read(k);
        addedge(k+1,i);
      end;
    end;
end;

begin
  while true do begin
    read(n);
    if n=0 then break;
    total:=0;
    fillchar(first,sizeof(first),0);
    fillchar(last,sizeof(last),0);
    into;
    atfirst;
    work;
  end;
end.

递归

type
  arr=record
    toward,next:longint;
  end;
var
  edge:array[0..1000005]of arr;
  first,sg:array[0..1005]of longint;
  chose:array[0..1005]of boolean;
  n,total:longint;


procedure addedge(j,k:longint);
begin
  inc(total);
  edge[total].toward:=k;
  edge[total].next:=first[j];
  first[j]:=total;
end;

function getsg(x:longint):longint;
var
  i:longint;
  chose:array[0..1001]of boolean;
begin
  if sg[x]>=0 then exit(sg[x]);
  fillchar(chose,sizeof(chose),false);
  i:=first[x];
  while i>0 do begin
    chose[getsg(edge[i].toward)]:=true;
    i:=edge[i].next;
  end;
  i:=0;
  while chose[i] do inc(i);
  sg[x]:=i;
  exit(i);
end;

procedure work;
var
  i,ans,m:longint;
begin
  while true do begin
    read(m);
    if m=0 then break;
    ans:=0;
    while m>0 do begin
      dec(m);
      read(i);
      ans:=ans xor getsg(i+1);
    end;
    if ans>0 then writeln('WIN')
      else writeln('LOSE');
  end;
end;

procedure into;
var
  i,j,k:longint;
begin
  for i:=1 to n do begin
      read(j);
      while j>0 do begin
        dec(j);
        read(k);
        addedge(i,k+1);
      end;
    end;
end;

begin
  while true do begin
    read(n);
    if n=0 then break;
    total:=0;
    fillchar(first,sizeof(first),0);
    fillchar(sg,sizeof(sg),255);
    into;
    work;
  end;
end.

这次递归快了一点点

 【poj2068】Nim

（为什么题目都要叫nim？而且这题和nim没什么关系）由于是一个不公平游戏，所以就用dp暴力求。方法还是一样，如果有一个后继是失败那么现在为必胜，如果没有那么现在为必败。

var
  num:array[0..50]of longint;
  dp:array[0..50,0..10001]of longint;
  sum,n,i:longint;

function min(x,y:longint):longint;
begin
  if x<y then exit(x);
  exit(y);
end;

function dfs(x,y:longint):longint;
var
  i:longint;
begin
  if x>n<<1 then x:=1;
  if dp[x,y]>=0 then exit(dp[x,y]);
  for i:=1 to min(num[x],y) do
    if dfs(x+1,y-i)=0 then begin
      dp[x,y]:=1;
      exit(1);
    end;
  dp[x,y]:=0;
  exit(0);
end;

begin
  while true do begin

    read(n);
    if n=0 then break;
    read(sum);
    for i:=1 to n<<1 do read(num[i]);
    fillchar(dp,sizeof(dp),255);
    for i:=1 to n<<1 do dp[i,0]:=1;
    writeln(dfs(1,sum));
  end;
end.

【poj3480】John

反nim，具体见hzwer大神http://hzwer.com/1950.html

bzoj1874: [BeiJing2009 WinterCamp]取石子游戏

bzoj2463: [中山市选2009]谁能赢呢？

POJ  3537Crosses and Crosses

【poj3710】

kpm神写法

type
  arr=record
    toward,next:longint;
  end;
var
  edge:array[0..300]of arr;
  num,sg,fa,first:array[0..3000]of longint;
  tt,ans,i,j,k,n,m,total:longint;

procedure addedge(j,k:longint);
begin
  inc(total);
  edge[total].toward:=k;
  edge[total].next:=first[j];
  first[j]:=total;
end;

function cal(l,x:longint):longint;
var
  i,too:longint;
begin
  i:=first[x];
  num[x]:=l;
  while i>0 do begin
    too:=edge[i].toward;
    if (too<>fa[x]) and (num[too]>0) and (num[too]<l) then begin
        if (l-num[too]) and 1=1 then
          sg[x]:=num[too]-l
        else sg[x]:=num[too]-l+1;
        exit(sg[x]);
      end;
    if (num[too]=0) or (num[too]=l+1) then begin
      fa[too]:=x;
      sg[x]:=sg[x] xor (cal(l+1,too)+1);
    end;
    i:=edge[i].next;
  end;
  exit(sg[x]);
end;

begin
  while not eof do begin
    ans:=0;
    readln(tt);
    while tt>0 do begin
      dec(tt);
      readln(n,m);
      total:=0;
      fillchar(first,sizeof(first),0);
      fillchar(sg,sizeof(sg),0);
      fillchar(fa,sizeof(fa),0);
      fillchar(num,sizeof(num),0);
      for i:=1 to m do begin
        readln(j,k);
        addedge(j,k);
        addedge(k,j);
      end;
      ans:=ans xor cal(1,1);
    end;
    if ans>0 then writeln('Sally')
      else writeln('Harry');
  end;
end.

自己傻逼想成了环套树dp写，然后没调出来

type
  arr=record
    toward,next:longint;
  end;
var
  edge:array[0..50000]of arr;
  first,dep,low,dfn,sg,fa:array[0..10000]of longint;
  tt,n,m,total,time,ans:longint;

procedure addedge(x,y:longint);
begin
  inc(total);
  edge[total].toward:=y;
  edge[total].next:=first[x];
  first[x]:=total;
end;

procedure tarjan(x:longint);
var
  i,too,j:longint;
begin
  inc(time);
  dfn[x]:=time;
  low[x]:=time;
  i:=first[x];
  sg[x]:=0;
  while i>0 do begin
    too:=edge[i].toward;
    if too<>fa[x] then begin
      if dfn[too]=0 then begin
        dep[too]:=dep[x]+1;
        fa[too]:=x;
        tarjan(too);
        if low[too]<low[x] then low[x]:=low[too];
      end
      else
        if dfn[too]<low[x] then low[x]:=dfn[too];
      if dfn[x]<low[too] then sg[x]:=sg[x] xor (sg[too]+1);
    end;
    i:=edge[i].next;
  end;
  i:=first[x];
  j:=0;
  while i>0 do begin
    too:=edge[i].toward;
    if (fa[too]<>x) and (dfn[x]<dfn[too]) then
      if (dep[too]-dep[x]+1) and 1=1 then inc(j);
    i:=edge[i].next;
  end;
  if (j and 1=1) then sg[x]:=sg[x] xor 1;
end;


procedure into;
var
  i,j,k:longint;
begin
  total:=0;
  fillchar(first,sizeof(first),0);
  fillchar(dfn,sizeof(dfn),0);
  fillchar(low,sizeof(low),0);
  readln(n,m);
  for i:=1 to m do begin
    readln(j,k);
    addedge(j,k);
    addedge(k,j);
  end;
end;

function work:longint;
begin
  time:=0;
  dep[1]:=1;
  tarjan(1);
  exit(sg[1]);
end;

begin
  readln(tt);
  ans:=0;
  while tt>0 do begin
    dec(tt);
    into;
    ans:=ans xor work;
    writeln(ans);
  end;
  if ans>0 then writeln('Sally')
    else writeln('Harry');
  readln;
end.

待填之坑

【poj1740】A New Stone Game（http://blog.csdn.net/niushuai666/article/details/6639977）

【vijos1655】萌萌的糖果博弈

【vijos1196】吃糖果游戏

【poj2505】A multiplication game（找胜负分界点）

【poj2484】A Funny Game（分析对称）