SRM710 div1 MagicNim(博弈论)
题目大意:
给出n+1堆石子,前n堆石子的数量是a[i],最后一堆只有1个石子,但是具有魔力
拿走该石子的一方可以选择接下来是进行普通的Nim游戏还是anti-nim游戏
问是先手必胜还是必败
首先拿全是1的情况熟悉一下规则
如果全是1,那么无论有几堆,先手都是必胜的
因为如果有奇数个1,那么Alice直接拿掉魔力石子,然后选择不改变游戏,那么他还是赢的
如果有偶数个1,那么Alice直接拿掉魔力式子,然后选择改变游戏,于是他还是赢的。
然后回忆一下anti-nim的先手必胜条件(这里的SG不考虑多魔法石子的那一堆)
SG为0,且所有石子均为1
SG不为0,且存在一堆石子大于1
所以,如果不全是1,且SG为0的话,Alice是必输的,因为他取魔力石子后,仍然无法改变必输的情况
所以现在情况只有不全是1,且SG不为0
注意到这个时候任何一方如果直接取魔力石子,都是必败的
所以双方应该会保持SG不为0,然后进行对峙
首先考虑所以石子的数量不超过3
那么SG函数的值就只有3个,1,2,3
当SG为1或3的时候,肯定有一种取法使得SG为2
而SG为2的最终情况是2附加一个魔力石子,这种情况是必败的
所以当石子的数量不超过3时,SG=2先手必败,反之必胜
接下来考虑石子的数量超过3,也就是有4和4以上的数
那么SG函数的值可以分成1和超过1的那些情况
如果当前SG值为1,那么只能把它变成超过1的值,然而对手又可以把它变回到1
我们考虑假设只有1个超过3的数,那么这时候SG值肯定是大于3的
直接改变这个数,我们可以使得接下来的局面变成SG=2
也就是说,如果只有1个超过3的数,那么就是先手必胜
那么如果SG值为1,且我们知道存在超过3的数,那么超过3的数的数量必定至少有2个
也就是说,经过不断地对峙,原来SG值为1的话,现在SG值仍然为1
但是经过了很多减少,一定会达到这个局面
即SG值为1,且超过3的数量只有2个
当这2个其中的一个数减到4以下时,就变成了只有1个超过3的数
即SG->1->3以上->2(最终结果)
也就是说SG如果为1,必定会转化成2,那么SG=1就是必败局面,而其他情况是必胜局面
最后结论就是
如果有大于3的数,那么SG=1必败
如果没有,那么SG=2必败
(PS:题解的思路没有太明白,不知道是怎么想到右移1位然后分类的,然后莫名分类就分出来了orz)
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream> using namespace std; class MagicNim {
public:
string findWinner(vector<int> a) {
sort(a.begin(), a.end());
int n = a.size(), sg = ;
for(int i = ; i < n; i++) sg ^= a[i];
if(a[n-] >= ) return (sg == ? "Bob" : "Alice");
else return (sg == ? "Bob" : "Alice");
}
};
最新文章
- javascript测试
- util包下的Date与sql包下的Date之间的转换
- [Educational Codeforces Round 16]E. Generate a String
- shell.application asp多种组件执行cmd 单文件版本
- jquery事件切换hover/toggle
- room-views-用窗口颜色清除背景(Clear Background with Window Colour)选项
- bnuoj 29368 Check the Identity(栈)
- POJ 2431 Expedition (STL 优先权队列)
- IE中的事件对象
- 可能是最简单的方式:利用Eclipse创建基于Maven的Web项目
- Spring Boot 之构建Hello Word项目
- raft如何实现Linearizable Read
- Jenkins: 执行 PowerShell 命令
- java中需要注意的小细节
- vue项目中遇到的问题
- 计算机爱好者协会技术贴markdown第一期
- RabbitMQ 任务分发机制
- Google Chrome 中安装 PostMan 扩展
- Android-Recyclerview-使用分割线
- python3 scrapy 爬取腾讯招聘