http://acm.hdu.edu.cn/contests/contest_show.php?cid=887

1003 - Slime and Stones

 

题意：两个人，两堆石子，每次操作可以从某一堆拿任意多个，或者从两堆分别拿 x，y 个，要求 ∣x−y∣≤k|x-y|\le k。先拿完的胜，问先手能否必胜。

扩展威佐夫博弈

扩展威佐夫博弈裸题，设 ∣x−y∣<d|x-y|<d，则第 kk 个奇异局势为 (⌊2−d+d2+42k⌋,⌊2+d+d2+42k⌋)\left ( \left \lfloor \frac{2-d+\sqrt{d^2+4}}{2} k \right \rfloor,\left \lfloor \frac{2+d+\sqrt{d^2+4}}{2}k \right \rfloor \right )，面对奇异局势的必败。

证明什么的咱也不会

就贴个大佬链接吧 https://www.cnblogs.com/Khada-Jhin/p/9609561.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e5 + 10;
const ll mod = 1e9 + 7;
int T;
int main() {
	scanf("%d", &T);
	while (T--) {
		ll a, b;
		double d;
		scanf("%lld%lld%lf", &a, &b, &d);
		if (a > b)swap(a, b);
		d += 1.0;
		ll k = (b - a) / d;
		ll x = (2.0 - d + sqrt(d*d + 4.0))*k / 2.0, y = (2.0 + d + sqrt(d*d + 4.0))*k / 2.0;
		if (x == a && y == b)puts("0");
		else puts("1");
	}
	return 0;
}