Java教程

博弈论

本文主要是介绍博弈论，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

emmmmm，是因为在一次训练赛中看到了一道题， 然后就去学了一遍单独发出来把
image
image
在nim博弈的定义和证明上算法进阶讲的还是挺详细的， 上道题
洛谷P5675 [GZOI2017]取石子游戏
根据以上定义， 当Alice取完石子后的异或值不为0， 那么一定是一种必败的情况， 假如所取第一堆的数量为\(a_i\)， 而其他的石子的异或值大≥\(a_i\), 那么无论Alice怎么取， 都不会使异或值为0， 我们再看数据范围， 每堆石子的数量最多是200， 不超过\(2^8\), 那么我们可以枚举出第一堆所取哪一堆和其他堆石子的状态，设f[i][j]表示，前第i堆石子的状态是j的方案数，吗当然， 要求n遍， 以为要枚举每一堆作为第一堆， 这样， 这道题就完美解决了

点击查看代码 
#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
int n, ans = 0, a[210], f[210][260];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	for (int i = 1; i <= n; ++i) {
		memset(f, 0, sizeof(f));
		f[0][0] = 1;
		for (int j = 1; j <= n; ++j) {
			for (int k = 0; k < 256; ++k) {
				if (i == j) f[j][k] = f[j - 1][k];
				else f[j][k] = (f[j - 1][k] + f[j - 1][k ^ a[j]]) % mod;
			}
		}
		for (int j = a[i]; j < 256; ++j) 
			ans = (ans + f[n][j]) % mod;
	}
	cout << ans << endl; 
	return 0;
}

我们继续看另一类博弈论游戏：
image

接下来我们引进SG函数
image

image

所以， 我们如果看到博弈论游戏， 可以先算出终止情况并赋值为0， 然后一步步的求出SG函数， 判断异或值， 注意的是一种情况的SG函数是根据所有子情况来算出的， 并且一定要看出等效的情况， 有时候abc和def其实是一样的， 这样会很节省时间
上训练赛的题

K. Alice and Bob-2
首先全为0的话肯定是必败的情况， 不为0的情况下我们就根据这两个条件暴力的去取数， 当然也必须要记忆化(PS: 在全为0的情况下， 我忘了return SG[x] = 0, 会T， 加上这句话后跑的飞快， 并且每次递归的时候记得排序， 因为是一种等效的情况， 否则会很浪费时间)

点击查看代码 
#include <bits/stdc++.h>

using namespace std;

int t, n; 
char ch[50];
map < vector < int > , int > SG; 

inline bool check(vector < int > x) {
	for (int i = 0; i <= 25; ++i) 
		if (x[i]) return false;
	return true;
}

inline int Find(vector < int > x) {
	if (SG.find(x) != SG.end()) return SG[x];
	if (check(x)) return SG[x] = 0;
	vector < int > a;
	for (int i = 0; i <= 25; ++i) {
		if (x[i]) {
			vector < int > vec = x;
			--vec[i];
			sort(vec.begin(), vec.end());
			a.push_back(Find(vec));
		}
	}
	for (int i = 0; i <= 25; ++i) {
		for (int j = 0; j <= 25; ++j) {
			if (i == j) continue;
			if (x[i] && x[j]) {
				vector < int > vec = x;
				--vec[i], --vec[j];
				sort(vec.begin(), vec.end());
				a.push_back(Find(vec));
			}
		} 
	}
	sort(a.begin(), a.end());
	for (int i = 0; ; ++i) {
		bool flag = false;
		for (int j = 0; j < a.size(); ++j) {
			if (i == a[j]) {
				flag = true;
				break;
			} else if (a[j] > i) break;
		} 
		if (!flag) return SG[x] = i;
	} 
}

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		int ans = 0;
		while (n--) {
			vector < int > v;
			for (int i = 0; i <= 25; ++i) v.push_back(0);
			scanf("%s", ch + 1);
			int len = strlen(ch + 1);
			for (int i = 1; i <= len; ++i) ++v[ch[i] - 'a'];
			sort(v.begin(), v.end());
			ans ^= Find(v);
		}
		if (ans > 0) puts("Alice");
		else puts("Bob");
	}
	return 0;
}
这篇关于博弈论的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航