博弈论1

关于博弈论

可参考以下博客：博弈论基础知识与SG函数

P2197 【模板】nim游戏

传送门

P2197 【模板】nim游戏

题目分析

nim博弈板子题，结论如下：

Code

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

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

int T;
int n,a[10050],f;

int main()
{
	T = read();
	while (T--)
	{
		n = read();
		for (int i = 1; i <= n; ++i)
			a[i] = read();
		f = a[1];
		for (int i = 2; i <= n; ++i)
			f = f ^ a[i];
		if (f)	printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

总结与反思

1. 要看清楚题目，别和我一样Yes和No打成YES、NO，然后还不看错在哪里，结果调了半天
2. 没了

P2252 [SHOI2002]取石子游戏|【模板】威佐夫博弈

传送门

P2252 [SHOI2002]取石子游戏|【模板】威佐夫博弈

题目分析

威佐夫板子，具体见上面的博客，不再赘述

Code

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

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

int a,b;
double gor=1.618;

int main()
{
	a = read(), b = read();
	if ((int)(abs(a - b) * gor) == min(a, b))
		printf("0\n");
	else printf("1\n");
	return 0;
}

总结与反思

1. 威佐夫博弈要用到黄金分割比，所以精度比较重要，本题数据不强，强行比较即可

P4101 [HEOI2014]人人尽说江南好

传送门

P4101 [HEOI2014]人人尽说江南好

算法分析

经分析我们可以得到：

如果优先合并使每个大于$1$的堆都是$m$，最后剩下的就是$n$，不管先手是继续合并还是两两合并，只要后手愿意，可以保证经过这两次操作较大堆只加了$2$

不管怎么取，石子的最终分布一定是：$m,m,m....($共$n/m$个$m)，n\%m($因为初始每堆1个$，$石头数不能超过$m)$

决定胜负的应该是最后一次合并时轮到的玩家，而这个正好与合并次数的奇偶性有关。

操作次数$=$合并之后完的数量为m的堆的数量 乘上$m-1$加上最后剩下的石头数量$-1$

Code

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

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

int T;
int n,m;

int main()
{
	T = read();
	while (T--)
	{
		n = read(), m = read();
		int ans = (n / m) * (m - 1) + ((n % m) ? (n % m - 1) : 0);
		if (ans & 1) printf("0\n");//判断奇偶
		else printf("1\n");
	}
	return 0;
}

总结与反思

1. 非模板博弈论，类似于数学题，需要手推，需要训练（见过各位大佬的构造，对于我来说真的是神来之笔orz ）