【2020年杭电暑假第九场】6869 Slime and Stones

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=6869

题意

有两堆石子,有两种拿取的方式,一:在一堆中拿任意多个石子,二:在两堆中拿相差不能超过k的石子个数,问最后谁赢。

思路

这题就是威佐夫博弈的扩展,本来的威佐夫博弈是k=0,但是这里,k>=0,那该怎么办呢?

还是从最开始的思路推起,对于两堆的石子分别为x和y时(x<y):

d=0时,第k个奇异局势为$([\frac{1+\sqrt 5}{2}k],[\frac{3+\sqrt 5}{2}k]),k=y-x$

这是要求$dx-dy<1$

这是根据Betty定理推出来的,$\frac{1}{x}+\frac{1}{x+1}\;=\;1$,这里的一个正解为$\frac{1+\sqrt 5}{2}$,只要判断$\frac{1+\sqrt 5}{2}*(y-x)==x \&\& \frac{3+\sqrt 5}{2}*(y-x)==y$就代表先手必输,一般的模板只要求其中的一个条件即可,因为d=0不需要考虑精度问题,但是当d!=0时,考虑精度问题,还是两个条件都判断一下。

d>0时,第k个奇异局势为$([\frac{2-d+\sqrt{d^2+4}}{2}k],[\frac{2+d+\sqrt {d^2+4}}{2}k]),k=\frac{y-x}{d}$,x和y也就相差个dk,就是上面为什么可以取两个条件。

{这里要求$dx-dy<d$

根据Betty定理,这里的解为$\frac{1}{x}+\frac{1}{x+d}=1$,所以我们只需要判断以下两个条件即可。

$$[\frac{2-d+\sqrt{d^2+4}}{2}k]==x\;\;\&\&\;\;[\frac{2+d+\sqrt {d^2+4}}{2}k]==y(先手必输)$$

注意d输入之后要++,这里的k是$\frac{y-x}{d}$,向下取整,所以由于精度问题,需要判断两个条件更精准。

参考:大佬

Code(109MS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x7f7f7f
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll mod = 998244353;
// const ll P = 1e9 + 7;
// const int maxn = 1e5 + 10;
// const double eps = 1e-6;

void weizuofu()
{
ll a, b;
double k;
scanf("%lld%lld%lf",&a,&b,&k);
k += 1.0;
if(a > b)
swap(a , b);
ll temp = (b - a) / k;
ll ans1 = temp * ((sqrt(4.0 + k * k) - k + 2.0) / 2.0);
ll ans2 = temp * ((sqrt(4.0 + k * k) + k + 2.0) / 2.0);
if(ans1 == a && ans2 == b)
printf("0\n");
else
printf("1\n");
}

void solve() {
int T;
scanf("%d",&T);
while(T--) {
weizuofu();
}
}

signed main() {
ios_base::sync_with_stdio(false);
//cin.tie(nullptr);
//cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
signed test_index_for_debug = 1;
char acm_local_for_debug = 0;
do {
if (acm_local_for_debug == '$') exit(0);
if (test_index_for_debug > 20)
throw runtime_error("Check the stdin!!!");
auto start_clock_for_debug = clock();
solve();
auto end_clock_for_debug = clock();
cout << "Test " << test_index_for_debug << " successful" << endl;
cerr << "Test " << test_index_for_debug++ << " Run Time: "
<< double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
cout << "--------------------------------------------------" << endl;
} while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
solve();
##endif
return 0;
}

由于我一直没有注意到把&&写成,导致一直都在WA,但是一想到我是个傻逼,所有事情都迎刃而解了,哈哈哈!

本文作者:jujimeizuo
本文地址https://blog.jujimeizuo.cn/2020/08/18/hdu-6869/
本博客所有文章除特别声明外,均采用 CC BY-SA 3.0 协议。转载请注明出处!