时间戳

首页 > 技术文章 > 学习笔记 博弈论部分例题选讲

学习笔记 博弈论部分例题选讲

LovToLZX 2020-10-01 11:41 原文

部分例题选讲

【BZOJ1115 [POI2009]石子游戏Kam】

我们把相邻的石子差分一下

然后发现相邻石子堆之间的差值不可以<0

那么最终的结果就是差值均为0

然后我们思考一下

每拿走一堆石子 如何去使用差分求解

对于石子数

1 5 14 16 20

差分之后就是: 4 9 2 4

然后我们例如从第三堆中拿出3个

1 5 11 16 20

差分之后就是: 4 6 5 4

貌似就是从【2】中移了3个到【3】

继续手捯饬一下就可以发现

仅需差分之后 再用差分序列跑阶梯博弈即可

注:这里 用于最终是全部移动到n再移走 所以就是从n枚举奇数

/*-------------OI使我快乐-------------*/
int num[N];
int T,n;
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(T);
	while(T--)
	{
		read(n);
		for(R int i=1;i<=n;++i) read(num[i]);
		for(R int i=n;i>=1;--i) num[i]-=num[i-1];
		int ans=0;
		for(R int i=n;i>=1;i-=2) ans^=num[i];
		puts(ans ? "TAK":"NIE");
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

【luogu3185 [HNOI2007]分裂游戏】  【BZOJ1188】

最终的情况就是

只有最后第n堆有石子

由于当前石子堆会收到前面石子堆的影响

所以我们不可以讲一个一个堆分开讨论

而是将每一堆上的一个石子分开讨论

然后对于每一个石子堆再使用SG定理组合

由于异或存在自反性 所以实际上就是一个\(01\)序列

然后我们在使用SG定理进行大的组合

有解输出方案

我们从i取走一个石子 在分别往j以及k上放一个石子

由于都是等价于\(01\)序列 所以就是个进行了一次取反操作

还记得取火柴游戏吗 ? ? ?

我们使\(x\ \ =\ \ a_1\ \ xor\ \ a_2\ \ xor\ \ a_3\ \ xor\ \ ......\ \ xor\ \ a_n\)

那么取的就是$\ \ a_i\ \ $

使得\(\ \ a_1\ \ xor\ \ a_2\ \ xor\ \ a_3\ \ xor\ \ ......\ \ xor\ \ a_i\ \ xor\ \ x\ \ xor\ \ ......\ \ xor\ \ a_n\ \ =\ \ 0\)

并且\(a_i\ \ xor\ \ x\ \ <\ \ a_i\)

同理

我们使\(x\ \ =\ \ SG_1\ \ xor\ \ SG_2\ \ xor\ \ SG_3\ \ xor\ \ ......\ \ xor\ \ SG_n\)

注 : 异或前提是当前堆石子个数\(\ \&1\ !\ =\ 0\)

\(O(n^3)\)枚举然后疑惑就可以了

/*-------------OI使我快乐-------------*/
int n,T;
int num[30],SG[30];
bool ok[1010];
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    read(T);
    for(;T;--T)
    {
        read(n);
        for(R int i=1;i<=n;++i) read(num[i]),SG[i]=0;
        for(R int i=n-1;i;--i)
        {//i->(j,k)(i<j<=k) 处理SG(i)
         memset(ok,0,sizeof ok);
         for(R int j=i+1;j<=n;++j)
          for(R int k=j;k<=n;++k)
          ok[SG[j]^SG[k]]=1;//SG定理求解该组合后继状态的SG
         for(R int j=0;;++j)//mex运算
         if(!ok[j]) {SG[i]=j;break;} 
        }
//		for(R int i=1;i<=n;++i)
//		printf("%d\n",SG[i]);
        int res=0;
        for(R int i=1;i<=n;++i)
        if(num[i]&1) res^=SG[i];
        if(!res)
        {
            printf("-1 -1 -1\n0\n");
        }
        else
        {
        int nx=0,ny=0,nz=0,ans=0;
        for(R int i=1;i<=n;++i)
         for(R int j=i+1;j<=n;++j)
          for(R int k=j;k<=n;++k)
          if((res^SG[i]^SG[j]^SG[k])==0)
          {
          	++ans;
          	if(nx&&ny&&nz) continue;
          	nx=i;ny=j;nz=k;
          }
        printf("%d %d %d\n%d\n",nx-1,ny-1,nz-1,ans);  	
        }
    }
//	fclose(stdin);
//	fclose(stdout);
    return 0;
}

【luogu3235 [Hnoi2014]江南乐】  【BZOJ3576】

\(70\ \ pts\)

对于\(SG[\ i\ ]\)

若\(i\ <\ F\) 不存在后继状态 \(SG[\ i\ ]=0\)

若\(i\ >=\ F\) 我们可以把TA拆成\(2\ ,\ 3\ ,\ 4\ ,\ ......\ ,i\)个石子堆 并且是平均分原则

公式如下:

\(SG[\ i\ ]\ =\ mex\ |_{i=2}^{j} SG[\ \lfloor\frac{i}{j}\rfloor\ ]\ \ xor\ \ SG[\ \lfloor\frac{i}{j}\rfloor\ ]\ \ xor\ \ ......\ \ xor\ \ SG[\ \lfloor\frac{i}{j}\rfloor+1\ ]\ \ xor\ \ SG[\ \lfloor\frac{i}{j}\rfloor+1\ ]\)

\(SG[\ \lfloor\frac{i}{j}+1\rfloor\ ]\)存在\(i\%j\)个

那么\(SG[\ \lfloor\frac{i}{j}\rfloor\ ]\)存在\(j-i\%j\)个

异或存在自反性 所以我们直接判断即可

\(70\%\)的数据是\(a_i<=1000\)所以我们可以\(O(n^2)\)预处理\(SG\)函数

/*-------------OI使我快乐-------------*/
int T,F;
int n;
int num[N],SG[N];
bool ok[N],final[N];
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    read(T);read(F);
    for(R int i=F;i<=1010;++i)
    {
        memset(ok,0,sizeof ok);
        for(R int j=2;j<=i;++j)
        {
            int tmp,las,res=0;
            tmp=i/j;las=i%j;
            if(las&1) res^=SG[(i/j)+1];
            if((j-las)&1) res^=SG[(i/j)];
            ok[res]=1;
 		}
 		for(R int j=0;;++j) if(!ok[j]) {SG[i]=j;break;}
    }
    for(R int x=1;x<=T;++x)
    {
        read(n);
        for(R int i=1;i<=n;++i) read(num[i]);
        int ans=0;
        for(R int i=1;i<=n;++i) ans^=SG[num[i]];
        final[x]=(ans ? 1:0);
    }
    for(R int x=1;x<=T;++x)
    printf("%d ",(final[x] ? 1:0));
//	fclose(stdin);
//	fclose(stdout);
    return 0;
}

\(100\ \ pts\)

由于存在求解\(|_{j=2}^{i}\lfloor\frac{i}{j}\rfloor\)

所以我们十分自然的想到 使用数列分块

那么对于一个商相同的块

我们需要分别处理

\(i\%j\)以及\(j-i\%j\)

\(1).\)在 \(\lfloor\frac{i}{j}\rfloor\) 相同的情况下 对于当前的 \(i\%j\) 构成等差数列

\(2).\)在 \(1)\) 情况下 由于 \(j\) 也是等差变化 所以\(j-i\%j\)也构成等差数列

\(3).\)由于是奇偶性的讨论 按照等差数列的性质 在数列\(size>1\)时 我们仅需讨论序列数列的前两项

时间复杂度\(O(n\sqrt{n})\)

由于使用一般的计算SG会被卡常 所以使用SG时间戳优化

/*-------------OI使我快乐-------------*/
int T,F,tot;
int n;
int num[1010],SG[N],final[1010],ok[N];;
IL void calc(int now)
{
    int tmp,las;
    for(R int i=2,cdy=0,wzy=0,res=0;i<=now;i=las+1)
    {//数列分块
        tmp=now/i;las=now/tmp;
        //对于当前的块 i是左端点 las是右端点
        wzy=now%i;cdy=i-wzy;res=0;//处理第一项
        if(cdy&1) res^=SG[tmp];
        if(wzy&1) res^=SG[tmp+1];
        ok[res]=tot;
        las=min(las,now);
//		printf("%d -> %d\n",i,las);
        if(i+1<=las)
        {//size>1 处理第二项
            wzy=now%(i+1);cdy=(i+1)-wzy;res=0;
            if(cdy&1) res^=SG[tmp];
            if(wzy&1) res^=SG[tmp+1];
            ok[res]=tot;
        }
    }
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    read(T);read(F);
    for(R int i=F;i<=100000;++i)
    {
        ++tot;calc(i);
        for(R int j=0;;++j)//时间戳优化
        if(ok[j]!=tot) {SG[i]=j;break;}
    } 
//	for(R int i=1;i<=1001;++i)
//	printf("SG[%d]->%d\n",i,SG[i]); 
    for(R int x=1;x<=T;++x)
    {
        read(n);int ans=0;
        for(R int i=1,y;i<=n;++i) read(y),ans^=SG[y];
        final[x]=(ans ? 1:0);
    }
    for(R int i=1;i<=T;++i)
    printf("%d ",(final[i] ? 1:0));
//	fclose(stdin);
//	fclose(stdout);
    return 0;
}

【POJ2311 Cutting Game 】

题意

对于一个\(n*m\)的方格纸 两人轮流裁纸

一开始先手沿着一行或者一列裁剪

然后就是 成为两块纸

后手选择其中一块 然后按同样的原则去剪

就是这样

kkksc02

然后谁先裁出\(1*1\)的方格纸 谁就赢了\(2<=n,m<=200\)

解法

SG函数

如果有人裁出了\(1\ *\ n\)或者\(n\ *\ 1\)那么此人必败

所以\(SG[1][x]=SG[x][1]=0\ \ ​\)

\(O(n^2)\)枚举\(n,m\),然后再\(O(n)\)枚举切除的新边长\(k\)(2<=k<=(n-2),(m-2))

/*-------------OI使我快乐-------------*/
//
bool ok[1010];
int SG[210][210];
int n,m;
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	SG[1][1]=1;
	for(R int i=2;i<=201;++i)
	 for(R int j=2;j<=201;++j)
	 {
	 	memset(ok,0,sizeof ok);
	 	for(R int k=2;(i-k)>1;++k)
	 	ok[SG[i-k][j]^SG[k][j]]=1;//Multi-Nim定理合并
	 	for(R int k=2;(j-k)>1;++k)
	 	ok[SG[i][j-k]^SG[i][k]]=1;
	 	for(R int k=0;;++k) if(!ok[k]) {SG[i][j]=k;break;}//mex运算
	 }
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(SG[n][m]) puts("WIN"); 
		else puts("LOSE"); 
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

【POJ3710 Christmas Game 】

看上去十分的复杂

但是由于环同基础树之间只用一个公共点

所以使用Tanjan+缩点+判断奇偶即可

剩余的看代码

/*-------------OI使我快乐-------------*/
int to[N],nex[N],head[N],sta[N];
bool vis[N],bel[N],have[N];
int n,m,T,tot,top;
IL void init()
{
	memset(bel,0,sizeof bel);
	memset(vis,0,sizeof vis);
	memset(sta,0,sizeof sta);
	memset(head,0,sizeof head);
	memset(nex,0,sizeof nex);
	memset(to,0,sizeof to);
	memset(have,0,sizeof have);
	tot=1;top=0;
}
IL void add(int x,int y){to[++tot]=y;nex[tot]=head[x];head[x]=tot;}
IL int dfs(int now)
{
	vis[now]=1;int ans=0;
	sta[++top]=now;
	for(R int i=head[now];i;i=nex[i])
	{
		int v=to[i];
		if(have[i]) continue;
		have[i]=1;have[i^1]=1;
		int tmp;
		if(!vis[v]) tmp=dfs(v)+1;//如果当前的点符合链
		else//否则就是遇见了环
		{
		    int cdy=sta[top--];
		    while(cdy!=v)
				bel[cdy]=1,cdy=sta[top--];
			++top;
			return 1; //返回1的值
		}
		if(bel[v]) ans^=(tmp)&1;//如果是环的话  富森定理 按照奇偶性来缩点
		else ans^=tmp;//否则 克朗定理 合并分支
	}
	return ans;
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	while(scanf("%d",&T)!=EOF)
	{
		int res=0;
		for(R int q=1;q<=T;++q)
		{
			init();//常树比较大的初始化
			read(n);read(m);
			for(R int i=1,x,y;i<=m;++i)
			{
				read(x);read(y);
				add(x,y);add(y,x);
			}
			res^=dfs(1);//SG定理合并
//			printf("now is %d\n",res^dfs(1));
		}
		if(res) puts("Sally");
		else puts("Harry");
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

推荐阅读