首页 > 代码库 > uva 11249 - Game(组合游戏)

uva 11249 - Game(组合游戏)

题目链接:uva 11249 - Game

题目大意:给定K和N,表示有N轮游戏,每轮游戏给定两堆石子的个数,两人轮流操作,每次操作可以选择一堆取任意数量的石子,也可以选两堆取,要求两堆取的石子数之差的绝对值小于K,不能操作者为输,问先手的胜负情况。

解题思路:傻逼先手才一次取完,那样的话对手直接将另一堆取光不就傻逼了。所以先手就有一个取石子的最优策略,当两堆石子的数量差小于等K的时候,先手可以一次性取完所有的。
我们设f(x)为一堆石子的数量为x时的必败态,即x,f(x),为先手必败态,x<f(x),那么对于状态x,b,如果b>f(x)的,则一定是必胜态,因为先手可以将b取成f(x)。如果b<x,那么同样的可以将x取成f(b),那么就出现了x<b<f(x)的情况,所以根据这个限定,我们可以推导出f(x),利用单调的性质,这接从前一项获取f(x),以为当状态x,b无法转移成x-1,f(x-1)时,此时的b即为f(x),需要注意的是,我们的x<f(x),那么对应的,当x=f(t),t<x,那么f(x)=t

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 1e5;

int N, K, v[maxn+5];

void init () {
    memset(v, -1, sizeof(v));

    int mv = 0;
    v[0] = 0;

    for (int i = 1; i <= maxn; i++) {
        if (v[i] == -2)
            continue;

        int tmp = v[mv] + i - mv + K + 1;
        if (tmp > maxn)
            break;

        v[i] = tmp;
        v[tmp] = -2;
        mv = i;
    }
}

int main () {
    int cas, a, b;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d%d", &K, &N);
        init();

        for (int i = 0; i < N; i++) {
            scanf("%d%d", &a, &b);
            int p = min(a, b);
            int q = max(a, b);
            printf("%s\n", v[p] == q ? "LOSING" : "WINNING");
        }
        printf("\n");
    }
    return 0;
}