传送门: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++)
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); ##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 协议。转载请注明出处!