Luogu P4101 [HEOI2014]人人尽说江南好(博弈论)

题目链接：https://www.luogu.com.cn/problem/P4101

题意：输入T，表示T组样例，然后每组输入n,m，每堆最初使为1，每次能合并两堆，但是不能每堆不能超过m。‘

题解：我看题解也不是全然看懂了。

我们关注的使操作次数，奇数则先手赢，偶数则后手赢。这个还是比较好理解的。（总结一下，博弈论常规操作）。

最长操作次数与操作成n/m个m，1个n%m的情况（为0自动略去）

如果拉到最长的操作次数为奇数即先手必胜的话，那么不管对面怎么操作，都可以拉回来

同样如果最长的操作是对面必胜，不管我们怎么合并，都可以拉回来

所以只需要讨论最长操作次数。

先手胜：

m=1，2很明显。最长操作次数不变

m=3,先手先2，后手如果3那么就不管正和我意，如果为2，那就再合并一个3（剩一个2），次数无影响，然后后手2，我们继续3，依然无影响,,,持续下去2 2与3 1 操作次数不变。最后剩下的都是2 2 1（不然就是2 2那么先手输）,然后先手3就ok了。

m=4，先手2，后手3就4，后手2也4。总之能够将次数拉到最大！！！

m=5,先手2 ，后手2则4，然后后手2 我5，再2再4再5.。。其实我也没想很明白，提供一种思路吧]。

//很不严密的推论，只是整理了一下自己的思路。

代码：

#include <bits/stdc++.h>

#define ll long long
#define pi acos(-1)
#define pb push_back
#define mst(a, i) memset(a, i, sizeof(a))
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define dbg(x) cout << #x << "===" << x << endl
using namespace std;
template <class T> void read(T &x) {
    T res = 0, f = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (isdigit(c)) {
        res = (res << 3) + (res << 1) + c - '0';
        c = getchar();
    }
    x = res * f;
}
void print(ll x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
const ll maxn = 20 + 10;
const ll mod = 1e9 + 7;

ll n, m;
// ll gcd(ll a,ll b){return (b==0)?a:gcd(b,a%b);}
// ll qpow(ll a,ll p,ll mod){ll
// ans=1;a=a%mod;while(p){if(p&1)ans=(ans*a)%mod;p>>=1;a=(a*a)%mod;}return ans;}
int main() {
    ll _s = 1;
    read(_s);
    for (ll _ = 1; _ <= _s; _++) {
        read(n),read(m);
		ll c=n/m,y=n%m;
		if(!y) y++;
		ll ans=(m-1)*c+y-1;
        puts(ans%2?"0":"1");
    }
    return 0;
}
/*
input:::

output:::

*/

 

本文地址：https://blog.csdn.net/I_have_a_world/article/details/109272950