uva 11249 - Game(組合游戲)

uva 11249 - Game(組合游戲)

題目鏈接：uva 11249 - Game

題目大意：給定K和N，表示有N輪游戲，每輪游戲給定兩堆石子的個數，兩人輪流操作，每次操作可以選擇一堆取任意數量的石子，也可以選兩堆取，要求兩堆取的石子數之差的絕對值小於K，不能操作者為輸，問先手的勝負情況。

解題思路：傻逼先手才一次取完，那樣的話對手直接將另一堆取光不就傻逼了。所以先手就有一個取石子的最優策略，當兩堆石子的數量差小於等K的時候，先手可以一次性取完所有的。
我們設f(x)為一堆石子的數量為x時的必敗態，即x，f(x),為先手必敗態，xf(x)的，則一定是必勝態，因為先手可以將b取成f(x)。如果b

#include 
#include 
#include 

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