2010-1105

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意是有很多堆高度不超过2的石头，石头有两种颜色，A只能拿白色的石头，B只能拿黑色的石头，如果拿的是最底下的石头，那么那整一堆石头都会崩溃掉。轮流取，直到有一个人没法取了，另一个人就赢，要求根据给出的石头的信息（每种石头堆的数量），判断A是否先后手的胜负。
[[BR]]
根据题目的说法，最多只有六种堆(从左到右表示堆的顶部到底部：

{{{
w, b, wb, bw, ww, bb
}}}
实际上一个ww（或一个bb）可以拆分成两个w（或两个b）。而一个w和一个b是可以互相抵消掉的，这样是不影响博弈结果的，一个wb和一个bw也能互相消掉，同样不影响结果。假设经过以上拆分和抵消之后，最后变成有m个w, m个wb，那么在纸上模拟一下博弈过程（B肯定先拿wb中的b，这样会使对方少一个w，A肯定会先拿wb中的w，减少对方的威胁），就可以发现当2m == n时，是先手必败的，而2m > n时，总是A胜，2m < n时，是B必胜。对bw, 和b的情况，也是类似的。
[[BR]]
我的代码：

{{{
#!cpp
#include <cstdio>
#include <cstring>
using namespace std;

int main() {
    int n;
    long long a, w, wb, b, bw;
    char buff[64];
    while (scanf("%d", &n) != EOF) {
        w = wb = 0;
        for (int i = 0; i < n; i++) {
            scanf("%s %lld", buff, &a);
            if (strcmp(buff, "w") == 0) {
                w += a;
            } else if (strcmp(buff, "b") == 0) {
                w -= a;
            } else if (strcmp(buff, "wb") == 0) {
                wb += a;
            } else if (strcmp(buff, "bw") == 0) {
                wb -= a;
            } else if (strcmp(buff, "ww") == 0) {
                w += 2 * a;
            } else {
                w -= 2 * a;
            }
        }
        bool win1, win2;
        if (w >= 0) {
            win1 = w * 2 > wb ? true : false;
            win2 = w * 2 >= wb ? true : false;
        } else {
            b = -w;
            bw = -wb;
            win1 = b * 2 < bw ? true : false;
            win2 = b * 2 <= bw ? true : false;
        }
        printf("%s %s\n", win1 ? "win" : "lose", win2 ? "win" : "lose");
    }
    return 0;
}

}}}

by vout

题意是有很多堆高度不超过2的石头，石头有两种颜色，A只能拿白色的石头，B只能拿黑色的石头，如果拿的是最底下的石头，那么那整一堆石头都会崩溃掉。轮流取，直到有一个人没法取了，另一个人就赢，要求根据给出的石头的信息（每种石头堆的数量），判断A是否先后手的胜负。

根据题目的说法，最多只有六种堆(从左到右表示堆的顶部到底部：

w, b, wb, bw, ww, bb

实际上一个ww（或一个bb）可以拆分成两个w（或两个b）。而一个w和一个b是可以互相抵消掉的，这样是不影响博弈结果的，一个wb和一个bw也能互相消掉，同样不影响结果。假设经过以上拆分和抵消之后，最后变成有m个w, m个wb，那么在纸上模拟一下博弈过程（B肯定先拿wb中的b，这样会使对方少一个w，A肯定会先拿wb中的w，减少对方的威胁），就可以发现当2m == n时，是先手必败的，而2m > n时，总是A胜，2m < n时，是B必胜。对bw, 和b的情况，也是类似的。

我的代码：

#include <cstdio>
#include <cstring>
using namespace std;
int main() {
    int n;
    long long a, w, wb, b, bw;
    char buff[64];
    while (scanf("%d", &n) != EOF) {
        w = wb = 0;
        for (int i = 0; i < n; i++) {
            scanf("%s %lld", buff, &a);
            if (strcmp(buff, "w") == 0) {
                w += a;
            } else if (strcmp(buff, "b") == 0) {
                w -= a;
            } else if (strcmp(buff, "wb") == 0) {
                wb += a;
            } else if (strcmp(buff, "bw") == 0) {
                wb -= a;
            } else if (strcmp(buff, "ww") == 0) {
                w += 2 * a;
            } else {
                w -= 2 * a;
            }
        }
        bool win1, win2;
        if (w >= 0) {
            win1 = w * 2 > wb ? true : false;
            win2 = w * 2 >= wb ? true : false;
        } else {
            b = -w;
            bw = -wb;
            win1 = b * 2 < bw ? true : false;
            win2 = b * 2 <= bw ? true : false;
        }
        printf("%s %s\n", win1 ? "win" : "lose", win2 ? "win" : "lose");
    }
    return 0;
}

by vout