【AT3939】[ARC091D] Strange Nim(博弈论)
2021/5/9 18:56:05
本文主要是介绍【AT3939】[ARC091D] Strange Nim(博弈论),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
点此看题面
- 有\(n\)堆石子,每堆石子初始有\(a_i\)个,且附带一个参数\(k_i\)。
- 每次可以从一堆石子(假设是第\(i\)堆,当前剩\(x_i\)个石子)中取出\(1\sim\lfloor\frac{x_i}{k_i}\rfloor\)个石子,判断谁必胜。
- \(n\le200,a_i,k_i\le10^9\)
\(SG\)函数
根据\(Nim\)游戏的基本知识我们知道可以分别求出每堆石子的\(SG\)函数,然后异或在一起就是全局的\(SG\)函数了。
一个显然的转移式:
\[SG(x)=\texttt{mex}_{i=1}^{\lfloor\frac xk\rfloor}SG(x-i) \]看起来很诡异,但我们仔细想想便会找到一个性质,就是\(x\)的前\(\lfloor\frac xk\rfloor+1\)位应该是一个\(0\sim \lfloor\frac xk\rfloor\)的排列!
但如果\(x\)是\(k\)的倍数时会存在例外,此时它的前\(\lfloor\frac xk\rfloor\)位是一个\(0\sim \lfloor\frac xk\rfloor-1\)的排列,因此\(SG(x)=\lfloor\frac xk\rfloor\)。
证明只需归纳即可,应该还是比较容易的。
那么我们可以列出一个简单的递推式:
\[SG(x)=\begin{cases}0&x<k,\\\lfloor\frac xk\rfloor&k|x,\\SG(x-\lfloor\frac xk\rfloor-1)&x>k\&\&k\not|x\end{cases} \]主要是考虑第三种转移,直接搞复杂度是\(O(k)\)的,如果\(k\)很大可能会挂。
但我们发现对于\(\lfloor\frac xk\rfloor\)相等的连续一段其实可以放一起转移,那么就只会转移\(O(\lfloor\frac ak\rfloor)\)次。
二者一结合,复杂度就是\(O(\sqrt a)\)的,正确了。
代码:\(O(n\sqrt a)\)
#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define Reg register #define RI Reg int #define Con const #define CI Con int& #define I inline #define W while using namespace std; int n;I int SG(CI x,CI k)//求SG函数 { if(x<k) return 0;if(!(x%k)) return x/k;//x<k和x是k倍数的两种情况 RI y=x/k*k,d=x/k+1,t=(x-y)/d;return SG(x-max(t,1)*d,k);//x/k相同的一段一起转移 } int main() { RI i,x,k,t=0;for(scanf("%d",&n),i=1;i<=n;++i) scanf("%d%d",&x,&k),t^=SG(x,k);//把每堆石子的SG函数异或起来 return puts(t?"Takahashi":"Aoki"),0; }
这篇关于【AT3939】[ARC091D] Strange Nim(博弈论)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01UniApp 中组件的生命周期是多少-icode9专业技术文章分享
- 2024-11-01如何使用Svg Sprite Icon简化网页图标管理
- 2024-10-31Excel数据导出课程:新手从入门到精通的实用教程
- 2024-10-31Excel数据导入课程:新手入门指南
- 2024-10-31RBAC的权限课程:新手入门教程
- 2024-10-31Svg Sprite Icon课程:新手入门必备指南
- 2024-10-31怎么配置 L2TP 允许多用户连接-icode9专业技术文章分享
- 2024-10-31怎么在FreeBSD上 安装 OpenResty-icode9专业技术文章分享
- 2024-10-31运行 modprobe l2tp_ppp 时收到“module not found”消息提醒是什么-icode9专业技术文章分享
- 2024-10-31FreeBSD的下载命令有哪些-icode9专业技术文章分享