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

93 阅读 0 评论 62 点赞

我是靠谱客的博主坚强火龙果，最近开发中收集的这篇文章主要介绍【2020年杭电暑假第九场】6869 Slime and Stones，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【2020年杭电暑假第九场】6869 Slime and Stones 扩展威佐夫博弈

- 题意
- 思路
- Code(109MS)

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

题意

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

思路

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

$还是从最开始的思路推起，对于两堆的石子分别为 x 和 y 时（ x < y ）：$

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

$这是要求 ∣ d x - d y ∣ < 1$

$这是根据 B e t t y 定理推出来的， 1 x + 1 x + 1 = 1 ，这里的一个正解为 1 + 5 2 ，只要判断 1 + 5 2 ∗ ( y − x ) = = x & & 3 + 5 2 ∗ ( y − x ) = = y 就代表先手必输，一般的模板只要求其中的一个条件即可，因为 d = 0 不需要考虑精度问题，但是当 d ! = 0 时，考虑精度问题，还是两个条件都判断一下。这是根据Betty定理推出来的，blue{frac{1}{x}+frac{1}{x+1};=;1}，这里的一个正解为blue{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，就是上面为什么可以取两个条件。$

$这里要求 ∣ d x - d y ∣ < d$

$根据 B e t t y 定理，这里的解为 1 x + 1 x + d = 1 ，所以我们只需要判断以下两个条件即可。根据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 是 y − x d ，向下取整，所以由于精度问题，需要判断两个条件更精准。 red{注意d输入之后要++}，这里的k是frac{y-x}{d}，向下取整，所以由于精度问题，需要判断两个条件更精准。$

参考：大佬

Code(109MS)

#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("0n");
    else
        printf("1n");
}


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;
}