CF138D World of Darkraft

题目链接

题意分析

首先我们一看就知道这是一道博弈论SG函数的题

但是由于斜线分割实在是不好处理 所以我们考虑一下转化坐标系

无标题.png

这样的话就很好做了

等等 这不就是曼哈顿转化为切比雪夫吗？

然后的话 我们就可以正常博弈论了

首先进行黑白染色 因为我们发现黑板染色之后棋盘就可以分为互不影响的两部分

无标题.png

然后我们分别对这两部分跑dfs求解SG值

这其中具体情况具体分析就可以了 详细请看代码

以前写的代码实在是太丑了

CODE:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x7fffffff
#define N 500008
#define IL inline
#define M 1008611
#define D double
#define ull unsigned long long
#define R register
using namespace std;
templatevoid read(T &a)
{
    T x=0,f=1;char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=0;ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+ch-'0';ch=getchar();
    }
    a=f?x:-x;
}
/*-------------OI使我快乐-------------*/
int n,m;
char s[51][51];
int SG[51][51][51][51][3];
IL int get_SG(int ax,int bx,int ay,int by,int flag)
{
	if(ax+1>=bx||ay+1>=by) return 0;
	if(SG[ax][bx][ay][by][flag]!=-1) return SG[ax][bx][ay][by][flag];
	int zjz=0;
	bool vis[110];memset(vis,0,sizeof vis);
	for(R int i=1;i<=n;++i)
	 for(R int j=1;j<=m;++j)
	 {
	 	if(((i+j)&1)==flag)
	 	{//如果当前枚举的棋子属于这一部分
	 		int cdy=i+j,wzy=i-j+m;//这里就是切比雪夫转化 各有各的转化方法
	 		if(cdy>ax&&cdyay&&wzy
博弈论数学坐标系转换

相关

组合游戏与博弈论基础

《博弈论》笔记

博弈论经典模型解析（入门级）

【YBT2022寒假Day7 B】格子染色（博弈论）（分类讨论）（找规律打表）

学习笔记 博弈论入门

读书笔记: 博弈论导论 - 14 - 不完整信息的静态博弈 机制设计

读书笔记: 博弈论导论 - 07 - 完整信息的动态博弈 预备知识

博弈论(Game Theory) - 01 - 前传之占优战略均衡

标签