[HEOI2014]人人尽说江南好博弈论

题面

题解

感觉这题挺神仙的，根据一些奇奇怪怪的证明可以得到：

最后的终止状态一定是\(m, m, m, m, .... n \% m\).

因此我们可以O(1)计算到终止状态所需步数，然后根据奇偶性即可判断谁胜谁负。

#include<bits/stdc++.h>

using namespace std;

#define R register int

inline int read()

{

    int x = 0; char c = getchar();

    while(c > '9' || c < '0') c = getchar();

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x;

}

void work()

{

    int T = read(), t;//先手必胜为0，后手必胜为1

    for(R i = 1; i <= T; i ++)

    {

        int n = read(), m = read();

        t = (n / m) * (m - 1) + (n % m > 0) * (n % m - 1);//把k个1合成k需要k - 1次

        printf("%d\n", 1 ^ (t & 1));

    }

}

int main()

{

//	freopen("in.in", "r", stdin);

    work();

//	fclose(stdin);

    return 0;

}

巴特西

[HEOI2014]人人尽说江南好博弈论

题面

题解

最新文章

热门文章

巴特西

[HEOI2014]人人尽说江南好 博弈论

题面

题解

最新文章

热门文章

[HEOI2014]人人尽说江南好博弈论