Category: 博弈论

【Vijos 1655】萌萌的糖果博弈

Qizy 1 Comment

题目传送门：https://vijos.org/p/1655

这个题嘛，暴力打印一下40以内的情况如下：
78973673526
不难发现，个位为2,3,7,8的话，则为先手必败
于是乎，读入+输出即可

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 100000;

char s1[MAXN],s2[MAXN];
int l1,l2;

inline bool leg(int c){
	return c == 2 || c == 3 || c == 7 || c == 8;
}

int main(){
	while (scanf("%s%s",s1+1,s2+1) == 2){
		l1 = strlen(s1+1); 
		l2 = strlen(s2+1);
		if (leg(s1[l1]-'0') && leg(s2[l2]-'0')) cout<<"SheepDaddy"<<endl;
		else cout<<"MengMeng"<<endl;
	}
	return 0;
}

【BZOJ 1022】[SHOI2008] 小约翰的游戏John

Qizy Leave a comment

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1022

anti-nim游戏，证明的话，网上到处都是，不过我还想是想自己证一下，证明如下：

结论：
1）所有堆中石子的个数都为1：如果NIM和为0，则先手必胜，否则后手必胜
2）有至少一堆的石子个数大于1，如果NIM和大于0，则先手必胜，否则后手必胜

证明：
1）如果所有堆中石子数都为1：
不难看出决策也唯一，结论显然成立
2）有至少一堆的石子个数大于1：
如果NIM和大于0，显然先手可以通过调整使最高的1为1的那堆石子，使NIM和变为0，使得先手必败，故先手必胜
如果NIM和为0，则先手无论调整任意一堆石子的个数，都会使NIM和变为大于0，使得先手必胜，故先手必败
该条证明，看似是循环证明，但实际上，堆中的石子数一直在减少，所以我们可以加上如下边界条件，使得该证明严密：
不难发现，大于1的堆数在慢慢减少，总有一个时刻，只会有一堆的石子数大于1。明显，此时的NIM和不为0。
显然现在的先手可以控制留下奇数个单石子堆或是偶数个。这将直接决定游戏的胜负。也就是说谁进入“只有一个多石子堆的状态”谁胜
明显，该状态符合NIM和大于0的情况，符合该情况中描述的先手必胜。而NIM和不为0的情况，也将间接转移进入该情况。
所以这个证明过程，不会一直循环下去，且结果确定。

哎，这个证明我自己都觉得是乱搔，大家还是看论文里的证明吧：
http://oi.cyo.ng/wp-content/uploads/2016/08/sg_jiazhihao.pdf

#include<iostream>
#include<cstdio>
using namespace std;

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

int main(){
	int T = read(); while (T--) {
		int n = read(),sg=0,tag=0;
		for (int i=1,tmp;i<=n;i++) {
			tmp = read(); sg ^= tmp;
			if (tmp > 1)  tag = 1;
		}
		if ((!sg && !tag) || (sg && tag)) printf("John\n");
		else printf("Brother\n");
	}
	return 0;
}

【NOI五连测】[D2T1] 啊

Qizy Leave a comment

题目传送门：http://pan.baidu.com/s/1hsLh92W
OJ传送门：http://oi.cdshishi.net:8080/Problem/1712

这一道题，我一眼看到的时候，也是“啊”的。博弈论？不会啊QAQ
最后只能打了暴力，结果还打错了QAQ

来说一说正解。
我们定义三种节点：
1.无名必胜
2.有名必胜
3.先手必胜

再来讨论一下这三种节点间的关系：
假如一个节点的儿子中，1、2两种类型的节点一样多，则为类型3
否则，1、2哪种多，该节点就是那种节点

于是搞一个树形DP，就可以搞出根节点的类型
显然，如果是类型3，则无解
如果是类型2，则只有部分节点可选
如果是类型1，则全部的叶子结点都可选

另外，本题还要注意，因为非叶子结点的颜色，最终会取决于它儿子节点的颜色
所以，第一步走的节点，一定是叶子结点，否则，并没有什么卵用QAQ

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int MAXN = 100000+9;

int n,vout,que[MAXN],type[MAXN],num[MAXN][3];
vector<int> G[MAXN];

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

inline void init(){
	n = read();
	for (int i=1;i<=n;i++) G[i].clear(), num[i][0] = num[i][1] = num[i][2] = 0;
	for (int i=1;i<=n;i++) G[read()].push_back(i);
	for (int i=1;i<=n;i++) type[i] = read() + 1;
	
	int fro,bak; que[fro=bak=1] = 1;
	while (fro < n) {
		int w = que[bak++];
		for (int i=0;i<(int)G[w].size();i++)
			que[++fro] = G[w][i];
	} 
}

void GetAns(int w){
	if ((int)G[w].size() == 0) {
		if (type[w] == 0) que[++vout] = w;
	} else {
		int t = num[w][2] - num[w][1];
		if (t <= 1 && t >= 0) for (int i=0;i<(int)G[w].size();i++)
			GetAns(G[w][i]);
	}
}

int main(){
	freopen("ah.in","r",stdin);
	freopen("ah.out","w",stdout);
	int T; cin>>T;
	while (T--) {
		init();
		for (int k=n,i=que[k];k;i=que[--k]){
			if ((int)G[i].size() == 0) continue;
			else { 
				for (int j=0;j<(int)G[i].size();j++) num[i][type[G[i][j]]]++;
				if (num[i][2] == num[i][1]) type[i] = 0;
				else if (num[i][1] > num[i][2]) type[i] = 1;
				else type[i] = 2;
			}
		} if (type[1] == 1) {
			int tot = 0; for (int i=1;i<=n;i++) if ((int)G[i].size() == 0 && type[i] == 0) que[++tot] = i;
			printf("%d ",tot); for (int i=1;i<=tot;i++) printf("%d ",que[i]); cout<<endl;
		} else if (type[1] == 0) {vout = 0, GetAns(1); sort(que+1,que+1+vout); cout<<vout<<' '; for (int i=1;i<=vout;i++) cout<<que[i]<<' '; cout<<endl;}  
		else printf("-1\n"); 
	}
	return 0;
}