luogu2594 [ZJOI2009]染色游戏
做法其他题解已经说得很清楚了,但似乎没有对于本题 SG 函数正确性的证明,我来口胡一下(
证明:
猜想:
\]
我们要用到一个结论: 局面的 SG 值等于局面中所有反面朝上的硬币单独存在时的 SG 值的异或和 。然而这个结论我不太会证()。我们暂且使用它而不证明。
首先当 \(i=1\lor j=1\) 成立时,本题相当于一维放硬币问题,其 SG 函数等同于一维的 \(lowbit(i)\)。因为 \(i\) 或 \(j\) 中至少有一个是 1,于是我们只需要将横纵坐标相加再 \(-1\) 即可消去为 1 的那一维。
对于其他情况我们使用数学归纳法:
首先对于 \(\operatorname{SG}(2,2)\) ,有以下几种选择方案(下图中 \(0/1\) 代表反转后分别是正面/反面朝上):
\(\begin{matrix} 0&0\\0&0 \end{matrix} ,\operatorname{SG}=0\)
\(\begin{matrix} 0&1\\0&0 \end{matrix} ,\operatorname{SG}=\operatorname{SG}(1,2)=2\)
\(\begin{matrix} 0&0\\1&0 \end{matrix} ,\operatorname{SG}=\operatorname{SG}(2,1)=2\)
\(\begin{matrix} 0&1\\1&0 \end{matrix} ,\operatorname{SG}=\operatorname{SG}(1,2)\space\operatorname{xor}\space \operatorname{SG}(2,1)=0\)
\(\begin{matrix} 1&1\\0&0 \end{matrix} ,\operatorname{SG}=\operatorname{SG}(1,1)\space\operatorname{xor}\space \operatorname{SG}(1,2)=3\)
\(\begin{matrix} 1&0\\1&0 \end{matrix} ,\operatorname{SG}=\operatorname{SG}(1,1)\space\operatorname{xor}\space \operatorname{SG}(2,1)=3\)
\(\begin{matrix} 1&1\\1&0 \end{matrix} ,\operatorname{SG}=\operatorname{SG}(1,1)\space\operatorname{xor}\space SG(1,2)\space\operatorname{xor}\space \operatorname{SG}(2,1)=1\)
\(\therefore \operatorname{SG}(2,2)=\operatorname{mex}\{0,2,2,0,3,3,1\}=4\),满足猜想。
还有一种特殊情况就是 \(i=2\land j>2\) 或 \(i>2\land j=2\),不难发现它们是等价的,因此这里我们只以 \(i=2\land j>2\) 为例。此时有 \(\operatorname{SG}(i,j-1)=2^{i+j-3},\operatorname{SG}(i-1,j)=\operatorname{lowbit}(j)\)。由 SG 函数定义有对于左上角为 \((1,1)\),右下角为 \((i,j-1)\) 的不包含右下角的矩形,在其中选择满足题目要求的连通块所得 SG 函数值域取遍 \([0,2^{i+j-3}-1]\)。因此在选择 \((i,j-1)\) 一点与上述矩形范围内取连通块可以取遍 \(2^{i+j-3}\space\operatorname{xor}\space[0,2^{i+j-3}-1]\) 即 \([2^{i+j-3},2^{i+j-2}-1]\) 范围内的值;可以证明在 \(j\ge3\) 时有 \(\operatorname{SG}(i-1,j)=\operatorname{lowbit}(j)\le 2^{i+j-4}\) (在 \(j=3\) 时有 \(\operatorname{lowbit}(3)=1\le 2^{i+j-4}\) ,而在 \(j>3\) 时有 \(\operatorname{lowbit}(j)\le j \le 2^{j-2}=2^{i+j-4}\)),因此在选择 \((i-1,j)\) 一点与上述矩形范围内取连通块可以取遍 \(\operatorname{lowbit}(j)\space\operatorname{xor}\space[0,2^{i+j-3}-1]\) 也即 \([0,2^{i+j-3}-1]\) 范围内的值(因为 \(\operatorname{lowbit}(j)\) 一位上为 1 的数异或后该位会变成 0,为 0 的数该位会变为 1,值域仍取遍)。做一下 mex 可得 \(\operatorname{SG}(i,j)=2^{i+j-2}\),符合猜想。
对于 \(i>2\land j>2\) 的 \((i,j)\),由数学归纳法有 \(\operatorname{SG}(i,j-1)=\operatorname{SG}(i-1,j)=2^{i+j-3}\),由 SG 函数定义有对于左上角为 \((1,1)\),右下角为 \((i,j-1)\) 的不包含右下角的矩形,在其中选择满足题目要求的连通块所得 SG 函数值域取遍 \([0,2^{i+j-3}-1]\)。因此除选择点 \((i,j)\)外,在 \((i,j-1),(i-1,j)\) 两点与上述矩形范围内取连通块可以取遍 \([0,2^{i+j-3}-1]\) 范围内的值,在 \((i,j-1)\) 一点与上述矩形范围内取连通块可以取遍 \(2^{i+j-3}\space\operatorname{xor}\space[0,2^{i+j-3}-1]\) 即 \([2^{i+j-3},2^{i+j-2}-1]\) 范围内的值,做一下 mex 可得 \(\operatorname{SG}(i,j)=2^{i+j-2}\),符合猜想。
证毕。
顺便挂一下代码:
#include <bits/stdc++.h>
using namespace std;
int T , n , m , sg[110][110] , init() , f[220] , flag;
string s;
inline void init()
{
for(int i = 1 ; i <= 100 ; i++ ) sg[i][1] = sg[1][i] = log2(i & (-i));
for(int i = 2 ; i <= 100 ; i++ )
for(int j = 2 ; j <= 100 ; j++ ) sg[i][j] = i + j - 2;
return ;
}
int main()
{
init();
scanf("%d" , &T);
while(T--)
{
memset(f , 0 , sizeof(f)); flag = 0;
scanf("%d%d" , &n , &m);
for(int i = 1 ; i <= n ; i++ )
{
cin >> s;
for(int j = 1 ; j <= m ; j++ )
{
if(s[j - 1] == 'T') f[sg[i][j]] ^= 1;
}
}
for(int i = 0 ; i <= 200 ; i++ )
{
if(f[i])
{
flag = 1;
break;
}
}
if(flag) printf("-_-\n");
else printf("=_=\n");
}
return 0;
}
/*
1
3 4
TTHH
THTH
TTHH
*/
最新文章
- Html-button和input的区别
- 基于vue的新组件开发
- Flex4的可视化显示对象
- Git管理项目实例说明-记录和跟踪项目
- MYSQL使用正则表达式过滤数据
- C/C++内存泄漏及检测 转
- 初学java之JFrame窗口模式
- D3D11 Debug Layer的bug
- ckeditor
- java新手笔记25 日期格式化
- myeclipse中控制台日志比实际晚8小时解决方法及java日志处理
- cc1plus: fatal error: emeralddb-pmdMain.d: No such file or directory
- HDU1250:Hat&#39;s Fibonacci
- 一步一步教你将开源项目上传到jcenter
- Android 分包 MultiDex 策略总结
- 七牛云音频转码准备工作之如何创建音视频处理私有队列pipeline
- 654. Maximum Binary Tree最大二叉树
- MySQL统计信息以及执行计划预估方式初探
- 项目Alpha冲刺--3/10
- TZOJ 2546 Electricity(去掉割点后形成的最大连通图数)
热门文章
- 解决Caused by: org.apache.ibatis.exceptions.PersistenceException:
- CVD-ALD前驱体材料
- CVPR2020论文点评: AdderNet(加法网络)
- AIFramework框架Jittor特性(上)
- BeetleX之Vue ElementUI生成工具
- Linux芯片驱动之SPI Controller
- Bind DNS服务——转发与区域记录更新
- 重新整理 .net core 实践篇—————文件系统[二十二]
- 【NX二次开发】通过两点创建单位向量
- sync.waitgroup ----等待goroutine的执行完成