博弈论

emmmmm,是因为在一次训练赛中看到了一道题, 然后就去学了一遍单独发出来把
博弈论
博弈论
在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;
}

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

接下来我们引进SG函数
博弈论

博弈论

所以, 我们如果看到博弈论游戏, 可以先算出终止情况并赋值为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;
} 
上一篇:c++学习 lambda


下一篇:MATLAB 计算点到直线的距离