lp4363 九省联考2018 一双木棋chess

快要省选了,需要学习一些乱搞操作。
在这里学习一下Min-Max对抗搜索。
首先了解一下Min-Max对抗搜索。
首先我们知道,对于一个零和有限信息确定性博弈游戏,我们可以将整个游戏的所有局面建成一个有向图。而在几乎所有此类游戏中,整个游戏的所有局面应当能组成一个DAG。
对于这样一个DAG,我们可以对它进行分层,最后得到的应当是一张分层图。这张分层图上的每一层象征着一方正在进行操作。
那么显然这个游戏的最终解是可以知道的。无非就是直接把整张图DFS一遍罢了。
然而,在绝大部分游戏中,这么做的复杂度都太大了,以至于根本无法接受。我们考虑一种被称为Min-Max对抗搜索的搜索方法。
我们首先定义先手方为Max方,后手方为Min方,然后设置一个搜索范围。那么每一个节点的值是这样确定的:
如果它的深度是搜索深度边缘,亦或者它干脆就是一个终止局面,那么它的值就是一个精心设计的估价函数的值。这个估价函数应当能够较好地估计整个局面倾向于哪一方。
如果这个节点是由Max方行动,那么它的值是所有子局面里的值的最大值,因为Max方会向对自己最有利的局面走。
如果这个节点是由Min方行动,那么它的值是所有子局面里的值的最小值,因为Min方会向对Max方最不利的局面,也就是对自己最有利的局面走。
这样就能够求得当前局面的权值,从而得到一个较优秀的决策支了。
本来打算学一下alpha-beta剪枝的,但是这一题好像不是很需要…

回到这一题,如果我们暴力储存每一个状态,那么很显然时间会爆炸。有没有更好的思路呢?
直觉告诉我们,一个格子放置的次序和答案是没有关系的。所以我们不妨假定当前放置的格子总是左上角的一整个块。这样状态数大概就在10^10以内了。
然而实际上并不需要这么多的状态。所以可以Hash以后用map离散化。

#include<iostream>
#include<cstdio>
#include<tr1/unordered_map>

inline int Max(int A,int B){
	return A>B?A:B;
}

inline int Min(int A,int B){
	return A<B?A:B;
}
const int INF=0x3f3f3f3f;
std::tr1::unordered_map<long long,int> mp;
int a[11][11],b[11][11],f[11],n,m;

inline long long hsh(){
	long long RT=0;
	for(int i=1;i<=n;++i){
		RT*=12;
		RT+=f[i];
	}
	return RT;
}

inline void ahsh(long long X){
	for(int i=n;i>=1;--i){
		f[i]=X%12;
		X/=12;
	}
}

inline int dfs(long long X,bool typ){
	if(mp.count(X)){
		return mp[X];
	}
	int RT=typ?-INF:INF;
	long long nw;
	ahsh(X);
	for(int i=1;i<=n;++i){
		if(f[i]<f[i-1]){
			++f[i];nw=hsh();
			RT=typ?Max(RT,dfs(nw,0)+a[i][f[i]]):Min(RT,dfs(nw,1)-b[i][f[i]]);
			--f[i];
		}
	}
	return mp[X]=RT;
}

void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&a[i][j]);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&b[i][j]);
		}
	}
	for(int i=0;i<=n;++i){
		f[i]=m;
	}
	mp[hsh()]=0;
	printf("%d\n",dfs(0,1));
}

int main(){
	init();
	return 0;
}

lp2197 NIM游戏

图文无关,因为空和白玩的游戏中没有一个是ICG类的。

NIM游戏是一类经典的博弈论题目。
众所周知,NIM游戏的结果就是把所有的答案异或起来即可。为什么可以这么做呢?
我们定义,对于一个「均衡组合博弈(ICG)」 ,我们定义两种局面状态:P(先手必败)和N(先手必胜)。
首先我们可以知道,在ICG中,博弈是一定会终止的;同时,终止局面是P局面。如果说一个局面的所有子局面都是N局面或者P局面,那么这个局面也一定是N局面或者P局面:这是因为N局面和P局面存在性质:
一个局面是P局面,当且仅当它的所有子局面都是N局面;一个局面是N局面,当且仅当它的所有子局面中存在一个是P局面。
这也就意味着,对于任何一种状态,我们都可以判定它是N状态还是P状态。
那么,初始状态的N-P性是可以判断的。
如何计算一个局面的N-P性呢?
我们定义一种运算,使得:
P局面经过这种运算只能变成N局面;
N局面经过这种运算可以变成P局面。
当我们用一个数列描述一个局面后,我们惊讶地发现:异或——这里指的是将局面中的每一个子部分异或起来——是满足这个性质的。
我们定义,异或值为零的局面是必败局面;异或值非0的局面是必胜局面。
我们将描述这个局面的数列异或起来,如果它等于零,那么任意一种「减少」操作——导致它的一个值减少的,一定会导向一种P局面;
而对于一种P局面,依据按位异或的特性,一定可以通过减少最大的数,来变更想变更的任意一位。
故而,我们发现,对于任意一种局面,我们可以用异或运算来判断它的N-P性。
事实上,两者之间并不存在那么直接的数学上的对应关系。可以将NIM游戏理解为一个数学模型。
这是一种指代关系。换句话说,为了更方便地处理它,
我们可以将这个局面转化为数学模型,而异或运算刚好满足其性质——这并不是说异或运算本身就是这个局面的变化。
当理解这一点之后,异或的意义就很显然了。

#include<iostream>
#include<cstdio>
using namespace std;
int n,a[10005];
void init(){
    scanf("%d",&n);
    int x=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        x^=a[i];
    }
    if(x){
        puts("Yes");
    }else{
        puts("No");
    }
    return;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

lp1290 欧几里德的游戏

这是一道基础的复杂博弈论题——我到现在都不是很能理解。
其实我也不太懂SG函数,我就口chao胡xi一下这题的做法吧。
对于\(x,y st: x<y\),我们定义对于x,y的SG函数SG(S),其中S是一个局面。 我们定义关于一个局面S的后继S’,使得S’可以从S转移得到。 所以我们定义一个集合T,包含了局面S的所有后继的SG值。 对于必败局面,我们令它的SG值为0,否则为1。 则\(SG(S)=mex(T)\),其中mex表示最小的不在集合中的非负整数。 所以, $$SG(x,y)=mex(SG(x,y-x),SG(x,y-2*x),$$

$$SG(x,y-3*x)…SG(x,y%x))$$ 我们又知道,对于其中的每一个SG函数,递推式都是成立的。 所以事实上,当\(x/y>1时,SG(x,y)=1\),这是因为当\(x/y==1\)始终是等于\(!(SG(y%x,x))\)
所以事实上\(SG(x,y)\)只取决于\(SG(x,y%x)\)的值。

#include<iostream>
#include<cstdio>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int a,b;

inline bool SG(int x,int y){
    if(!x){
        return 0;
    }
    if(y/x==1){
        return !SG(y%x,x);
    }else{
        return 1;
    }
}
void init(){
    scanf("%d%d",&a,&b);
    bool bo=SG(Min(a,b),Max(a,b));
    if(bo){
        puts("Stan wins");
    }else{
        puts("Ollie wins");
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

lp1288 取数游戏

事实上这是一道结论题。
首先,如果双方足够聪明,那么他们都不会回头。
这是因为,如果先手方往一个方向走,在背后留下了一个必败局面,那么后手方一定不会回头。
而如果先手方往一个方向走,在背后留下了一个必胜局面,那么他一定会选择破坏了这条边。
所以游戏必然成是链。
我们首先考虑边数为2的情况。此时先手必胜,这是因为如果先手足够聪明,那么他一定会选择把这整条边拿掉。此时后手输了。
而,对于边数是3的情况,先手必败。这是因为,先手无论取任何数,都会使得情况转化为边数为2的情况,那么后手可以走一步然后断绝通向必胜局面的路。
故而我们得知,如果起始点的两端有一条链的边数为偶,则先手必胜;否则后手必胜。

#include<iostream>
#include<cstdio>
using namespace std;
int n,a[20];
void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;++i){
        if(!a[i]){
            if(!(i&1)){
                puts("YES");
                return;
            }
            break;
        }
    }
    for(int i=1;i<=n;++i){
        if(!a[n-i+1]){
            if(!(i&1)){
                
                puts("YES");
                return;
            }
            break;
        }
    }
    puts("NO");
    return;

}
int main(){
    init();
    return 0;
}

 

lp1199 NOIP2009 三国游戏

首先我们定义最优配对:最优配对指的是,对于一个武将而言,与他默契值最高的武将。
其次我们定义次优配对,次优配对指的是,对于一个武将而言,与他默契值次高的武将。
那么我们知道,无论如何,人类能够选取的一定只能是一组次优配对,而不可能是一组最优配对。
当然人类一定可以取到次优配对中的最大值。这是因为电脑的操作一定会用于破坏人类取到最优配对,因此取到次优配对一定是可能的。
如果人类想要胜利,就必须防止电脑取到最优配对中比次优配对最大值更大的那些值。我们定义这样的值为「危险值」
如果危险值存在,那么组成它的两个部分一定都互为最优配对:证明如下。
如果组成危险值的两个部分不互为最优配对,那么危险值一定是两者中一者关于另一者的最优配对。
我们不妨设定甲武将是乙的最优配对,该配对是危险值,那么乙武将必须存在一个最优配对,使得该配对的值大于危险值。
这时候乙武将的次优配对一定大于等于危险值,但是这与危险值的定义矛盾。所以组成危险值的两个部分一定互为最优配对。
故而,我们发现,危险值一定是一种最优配对。
那么,当我们优先取得足以构成次优配对中的最大值的两个武将以后,电脑已经控制的一个武将总是不能构成危险值。
这是因为组成危险值的两个武将一定互为最优配对,而电脑已经控制的仅为其中的一个武将,并且与该武将构成最优配对的武将控制在玩家手中。
当游戏进行三步时,玩家已经控制了次优配对中的最大值,并且电脑不控制任何危险值,此时可以将游戏转化为
「电脑先手且必须控制危险值」的情况。
由于危险值总是需要由一组互为最优配对的武将构成,容易证明无论电脑如何选择,玩家都可以破坏危险值的构成。
因此,总是有解,且解总为次优配对中的最大值。

当然这一题还有一个实现难点在于读入,这里就不再细说。

#include<iostream>
#include<cstdio>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
/*
lp1199 三国游戏
*/
int n,f[505][505];
void init(){
    scanf("%d",&n);
    int mx,lmx,ans=0,x;
    for(int i=1;i<n;++i){
        for(int j=i+1;j<=n;++j){
            scanf("%d",&f[i][j]);
            f[j][i]=f[i][j];
        }
    }
    /*
    for(int i=1;i<n;++i){
        for(int j=1;j<n;++j){
            printf("%d ",f[i][j]);
        }
        puts("");
    }
    */
    for(int i=1;i<=n;++i){
        mx=0,lmx=0;
        for(int j=1;j<=n;++j){
            x=f[i][j];
            if(mx<x){
                lmx=mx;
                mx=x;
            }else{
                lmx=Max(lmx,x);
            }
        }
        ans=Max(ans,lmx);
    }
    puts("1");
    printf("%d",ans);
}
int main(){
    init();
    return 0;
}