一些碎碎念
之前阴差阳错看到了班固米上的一个帖子【招生广告】大家来发招生广告呀，或许是因为从高考以来，时间的麻醉效果也在缓慢地蔓延，不会有太剧烈的反应，自顾自地蒙头从一旁走过去成了我的遇事法则，只是给人一种魔幻的感觉，似乎自己不配在其中交谈，所谓人与人的差距，是货真价实的存在的。自己并没有异于常人的双商与能力乃至后天努力也不足这件事，比任何人都要清楚，告诉自己已经做得够好了，不知不觉又到了要为自己的偷懒买单的时候。最后扪心自问，我现在正处于两年前的自己所期望的位置上吗？
熟悉的取石子与ICG游戏
很多年前我曾经从杂志上看到一个取石子的必胜策略，那大概是我最早接触的也是最简单的Nim游戏，当时的我并没有对他进行严格的数学论证，知其然不知其所以然，抱着这样不求甚解的态度戏耍了几次同学之后便结束了这愚蠢的行为。
这里重现一下最基础的问题：
假设有一堆石子，共有x颗。两个玩家分别可以从当中取1颗、2颗或3颗，若某个玩家没有石子可取，那么他便输掉了游戏。那么当下状态是先手必胜还是后手必胜。
结论是当x是4的倍数时，后手必胜，否则便是先手必胜。下面是这个结论的证明。
首先设两种状态，分别为p状态和n状态，p状态代表当前情况下后手必胜，最显而易见的一个p状态便是当石子为0颗，这种情况下先手必败，n状态则相反，代表当前情况是一个先手必胜的情况，比方说剩余1，2，3颗石子的情况，都可以取光剩下的石子，让后手无石子可取。
引理
1.若某种状态可以通过某次操作转移到到p状态，那么当下状态必是n状态
2.若某种状态通过任意操作只能转移到n状态，那么当下状态必是p状态
引理1证明
若当下为先手，有某种操作可以使状态转移至p状态，那么只要转移到p状态便能使本次先手必胜，充分性得证。
若当下状态为n状态，那么胜方下回合将会成为后手，也就是必有一种方法使得下回合后手必胜，n的子节点中至少存在一种p状态，必要性得证。
引理2证明
若当下的任意操作都使得下回合先手必胜，也就是胜方在本回合是后手，本回合应为后手必胜，也就是p状态，充分性得证。
若当下的状态时后手必胜p状态，那么选择权并不在胜方手上，而下回合胜方成为先手时要求先手必胜，因此p状态的所有子节点都是先手必胜的n状态，必要性得证。
已知0时p状态，1，2，3时n状态，4的子节点是1，2，3，都是n状态，因此4是p状态，也就是后手必胜，用数学归纳法不难得出，所有4的倍数都是后手必胜的状态。这个问题便得到了证明。同理，如果规定能够取的石子数量不是1，2，3，而是任意奇数，或者任意一个随机的数列，同样可以通过以上的方法推导出所有x的状态，打表的时间复杂度是O(x)。
稍微拓展一下原始的问题，假设一开始有的不是一堆石子，而是n堆石子，那么又该如何计算？比方说有两堆数量都为x的石子，可以用一个二元组来表示。（0，0）显然是p状态，（0，1）（0，2）（0，3）都是n状态，（1，1）只有（1，0）一种子状态，因此（1，1）是p状态，（1，2）（1，3）（1，4）都是有（1，1）的子状态，因此他们都是n状态...这样推算下去，手写会很麻烦，程序更方便一些，处理的时间复杂度是O(x2)，当n堆石子的个数分别是a1a2...an时，所需要的时间就是O(a1a2...an)
这里有一个很优美的结论，当a1^a2^...^an==0时，是后手必胜的状态，否则为先手必胜。具体的证明马上就会说到。
SG函数的引入
证明
若当前的状态下a1^a2^...^an==0，如何证明他和p状态时等效的呢？由异或的性质，显然改变任何一个ai都会使得等式不成立。也就是会反转当前的状态，这与引理1是类似的，再来看引理2，若a1^a2^...^an!=0，是否恒存在一种操作ai=ai'使a1^a2^...^an==0，答案是肯定的，设a1^a2^...^an!==k，已知ai^k==a1^a2^...^an（去掉ai），则将ai变为ai^k，左边就变成了0，接下来的问题就是如何选一个ai使ai>ai^k，答案是选二进制最高位和k一样都为1，很显而易见，就不作详细说明了。到此为止只证明了充分性，至于必要性，为什么要将异或与博弈练习在一起，可以参考这篇帖子为什么会想到用异或来算SG函数？它的本质是什么？
下面介绍一种函数，他的名字叫做Sprague-Grundy函数，定义一种运算为mex运算，运算方式是取最小的不在当下集合中的非负整数。比方说mex({0,1,3,4})=2，mex({1,2,3})=0。而sg函数便是对当下节点，以其子节点的sg值为集合，做mex运算，拿上面的流程图来做例子。
其中右边的是sg值，可见，当sg(x)==0时，那个节点就是p状态。
写太多，有点累了...另外还有一个，整体的sg值是子游戏的sg值得异或和。下面贴一道题。
附上sg预处理的做法其实不用这么麻烦
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
const int mod=1e9+7;
int f[11]={1,2,4,8,16,32,64,128,256,512,1024};
int sg[1010],has[1010];
void getsg(int n){
int i,j;
memset(sg,0,sizeof(sg));
for(int i=1;i<=n;++i){
memset(has,0,sizeof(has));
for(int j=0;f[j]<=i;++j){
//if(i==1)
//cout<<sg[i-f[j]]<<endl;
has[sg[i-f[j]]]=1;
}
for(int j=0;j<=n;++j){
if(has[j]==0){
sg[i]=j;
break;
}
}
}
}
main(){
int n;
getsg(1000);
//for(int i=0;i<=10;++i)cout<<sg[i]<<" ";
//cout<<endl;
while(cin>>n){
if(sg[n])cout<<"Kiki"<<endl;
else cout<<"Cici"<<endl;
}
}
另外附一道div2的f题，改日再做解说
F. BareLee
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int maxn=2e5+10;
bool judge(int s,int e){
if(e%2){
if(s%2==0){
return true;
}else{
return false;
}
}else{
if(s<=e&&s>e/2){
if(s%2){
return true;
}else{
return false;
}
}else if(s<=e/2&&s>e/4){
return true;
}else return judge(s,e/4);
}
}
main(){
int t;
cin>>t;
vector<int>v[2];
int tt=t;
while(t--){
int s,e;
cin>>s>>e;
v[0].push_back(judge(s,e));
if(s>e/2)v[1].push_back(1);
else v[1].push_back(judge(s,e/2));
}
int w=0,l=1;
for(int i=0;i<tt;++i){
if(l){
if(v[0][i]==v[1][i]&&v[0][i]){
w=1;
l=1;
break;
}
else if(v[0][i]){
w=1;
l=0;
}else if(v[1][i]){
w=0;
l=1;
}else {
w=0;
l=0;
break;
}
}else if(w){
if(v[0][i]==v[1][i]&&v[0][i]==0){
w=1;
l=1;
break;
}
else if(!v[0][i]){
w=1;
l=0;
}else if(!v[1][i]){
l=1;
w=0;
}else{
w=0;
l=0;
break;
}
}
}
cout<<w<<" "<<l<<endl;
}
Comments | NOTHING