杭电多校第九场 1003 Slime and Stones 题解

题目大意

有两堆石头，每个人每回合可以在任意一堆取任意个或者从第一堆取x个，第二堆取y个，$|x-y|\leq k$，每人采取最佳策略，问先手是否必胜。

解题思路

这个题目就是扩展威佐夫博弈。

听都没听过。。

威佐夫博弈点这里。

威佐夫博弈就是这个题目k为0的情况。

当k不等于0的时候，可以得到式子，详解见这个博客。

懒得推了（其实是不会。。

得到正解之后的式子之后，二分b，如果没找到，则说明不在数列中，必赢，如果找到了，如果a也满足，则必输，否则必赢。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

ll a, b, k;

int solve() {
    k++;
    ll l, r;
    l = 0, r = 1e8 + 5;
    while (l <= r) {
        ll mid = (l + r) / 2;
        ll tmp = mid * ((sqrt((k - 2) * (k - 2) + 4 * k) - k + 2) / 2) + k * mid;
        if (tmp > b)    r = mid - 1;
        else if (tmp < b)    l = mid + 1;
        else return  a == (ll)(mid * ((sqrt((k - 2) * (k - 2) + 4 * k) - k + 2) / 2));
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--) {
        cin >> a >> b >> k;
        if (a > b) swap(a, b);
        int ans = solve();
        if (ans == -1 || !ans)    cout << 1 << endl;
        else cout << 0 << endl;
    }
    return 0;
}