POJ 2315 Football Game 题解《挑战程序设计竞赛》

POJ 2315 Football Game 

国足：两名球员轮流从N个球中挑出不多于M个射门，每个球半径都是R，离球门S。由于国脚技术高超，每次只能踢出L以内的距离。进最后一个球者胜，求谁有必胜策略？

4.2找出游戏的必胜策略 

Nim与Grundy数

跟傻逼打交道智商会下降，刷一题保护一下智商！

一读那错别字连篇又拗口的Chinglish就知道是POJ Monthly，果不其然，能把三句话交待完毕的意思写得那么漏洞百出真是难为出题人这家伙了。

如果思维活跃的话，会发现这题其实是一个强化的Nim游戏。如何看破呢？每个球到球门的距离除以周长得到一个数字k，向上取整，代表要踢多少圈才能进球。于是转换思维，将每个足球看做Nim游戏中一堆数目为k的石头堆。每次踢出距离不超过L，将L除以周长，向下取整，得到每次至多能拿的石头个数K。将每个k % (K+1)，可以简化每个石头堆上的石头数，因为你拿走x个，我可以拿走K+1-x个，抵消你的操作，使得游戏状态不变。每次可选不多于M个足球，即每次可选M座石头堆。

经典算法中，XOR=k₀^k₁^…^k_n-1，若为0，则先手必败，否则必胜。

XOR又称半加运算，即只执行加法而不执行进位。在原始Nim游戏中，只允许选取1堆，所以最终XOR的结果是以2为进制执行半加运算。在此处，每次可选M座石头堆，进制则为M+1。在实现的时候可以先不管进位，只做加法，最终对M+1求模，将carries去掉。

#include <cstdio>
#include <cstring>

using namespace std;

#define MAX_N  30
#define MAX_S  27   // The base 2 logarithm of 100000000 is 26.5754247591
#define PI        3.14159265358979323846264338327950288
int N, M, L, R;
int S[MAX_N], XOR[MAX_S];

/**
 * s是足球周长的几倍（不足1按1算）
 * @param s
 * @return
 */
int distance(const int& s)
{
    return (int) (s / (2 * PI * R)) + 1;
}

bool solve()
{
    memset(XOR, 0, sizeof(XOR));
    const int K = distance(L);          // 每堆石头最多拿走K-1个
    for (int i = 0; i < N; ++i)
    {
        int g = distance(S[i]) % K;     // Nim游戏中一座山上的石头个数
        for (int j = 0; g; ++j, g >>= 1)
        {
            XOR[j] += g & 1;            // 每一位执行二进制XOR操作中的加法部分
        }
    }

    for (int i = 0; i < MAX_S; ++i)     // 最后判断是否为0，但XOR进位位制是M+1
    {
        if (XOR[i] % (M + 1))
        {
            return true;
        }
    }
    return false;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    while (~scanf("%d%d%d%d", &N, &M, &L, &R))
    {
        for (int i = 0; i < N; ++i)
        {
            scanf("%d", S + i);
        }
        puts(solve() ? "Alice" : "Bob");
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2315 Football Game 题解《挑战程序设计竞赛》