2010-1076

从 Trac 迁移的文章

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

原文章内容如下：

== 题目大意 ==

桌面上有 4 张牌，两个拥有不太一样的换牌技能的人博弈，其中一个人的目的是让 4 张牌可以算出 24 点，另一个人是不让 4 张牌算出 24 点，问对于一个人，有无必胜策略。

== 简要算法 ==

算法分为两个步骤：
 1.  打表，暴力算出所有可能的 24 点情况，这个步骤大概需要 0.1 s
 2. 博弈，暴力搜索所有情况，按照比赛时使用的数据，这个步骤大约需要 0.1 s

== 参考程序 ==

这个版本的参考程序目前是 192 中已提交中最快的：

{{{
#!cpp
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <bitset>

using namespace std;

bitset<65536> v24;

inline double binop(double a, double b, int op) {
    switch(op) {
    case 0: return a + b;
    case 1: return a - b;
    case 2: return b - a;
    case 3: return a * b;
    case 4: return a / b;
    case 5: default: return b / a;
    }
}
inline bool t24(double a) {
    return a > 23.99999 and a < 24.00001;
}
void i24() {
    int a[5] = { 1 };
    int op[3];
#define FORA(i) for (a[i] = 1; a[i] < 11; a[i]++)
#define FOROP(i) for (op[i] = 0; op[i] < 6; op[i]++)
#define OP binop
    FORA(1) FORA(2) FORA(3) FORA(4) {
        int b[4] = {a[1], a[2], a[3], a[4]};
        sort(b, b + 4);
        int v = (b[0] + (b[1] << 4) + (b[2] << 8) + (b[3] << 12));
        if (v24.test(v)) continue;
        bool success = false;
        FOROP(0) FOROP(1) FOROP(2) 
            if  (
                t24(OP(OP(OP(a[1], a[2], op[0]), a[3], op[1]), a[4], op[2]))
                || t24(OP(OP(a[1], a[2], op[0]), OP(a[3], a[4], op[1]), op[2]))
                ) {
                success = true;
                goto i24_setbit;
            }
i24_setbit:
        if (success) v24.set(v);
    }
#undef FORA
#undef FOROP
}

struct Card {
    int n;
    char c;
    void read() {
        scanf("%d %c", &n, &c);
    }
};

struct State {
    Card d[4], p[2][4];
    const bool test() const {
        int ihc[4] = { d[0].n, d[1].n, d[2].n, d[3].n };
        sort(ihc, ihc + 4);
        int v = (ihc[0] + (ihc[1] << 4) + (ihc[2] << 8) + (ihc[3] << 12));
        return (v24.test(v) != 0);
    }
} state;

int k,m;
// return true if Sima Yi wins
bool gao(int who = 0, bool first_round = false) {
    // set win to 24 judge from desktop currently
    bool win = state.test(); 

    if (who) {
        // Zhang Jiao's turn, he wins if there is one way to win
        if (!win) return win;
        for (int i = 0; i < m; i++) {
            Card card = state.p[who][i];
            if (card.c == 'b') {
                // can use that card to swap a card in desktop
                for (int j = 0; j < 4; j++) {
                    // backup card at desktop and swap
                    Card card_backup = state.d[j];
                    state.d[j] = card;
                    state.p[who][i] = card_backup;
                    if (!gao(who ^ 1)) {
                    state.p[who][i] = card;
                    state.d[j] = card_backup;
                        return win = false;
                    }
                    // resume cards
                    state.p[who][i] = card;
                    state.d[j] = card_backup;
                }
            }
        }
    } else {
        if (first_round) win = false;
        if (win) return win;
        // Si Mayi's turn, he will win if there is just one way to win
        for (int i = 0; i < k; i++) {
            Card card = state.p[who][i];
            if (card.n > 0) {
                state.p[who][i].n = -1;
                // use that card to replace a card in desktop
                for (int j = 0; j < 4; j++) {
                    Card card_backup = state.d[j];
                    state.d[j] = card;
                    if (gao(who ^ 1)) {
                        state.d[j] = card_backup;
                        state.p[who][i] = card;
                        return win = true; 
                    }
                    state.d[j] = card_backup;
                }
                // resume that card
                state.p[who][i] = card;
            }
        }
    }
    return win;
}

int main(int argc, char const* argv[])
{
    // init 24, 0.13 s
    i24();

    int tc;
    scanf("%d", &tc);
    for (int ti = 0; ti < tc; ti++) {
        for (int i = 0; i < 4; i++)  state.d[i].read();
        scanf("%d%d", &k, &m);
        for (int ki = 0; ki < k; ki++) state.p[0][ki].read();
        for (int mi = 0; mi < m; mi++) state.p[1][mi].read();

        if (gao(0, true) || gao(1)) puts("Sima Yi Wins!");
        else puts("Zhang Jiao Wins!");
    }
    return 0;
}
}}}

题目大意

桌面上有 4 张牌，两个拥有不太一样的换牌技能的人博弈，其中一个人的目的是让 4 张牌可以算出 24 点，另一个人是不让 4 张牌算出 24 点，问对于一个人，有无必胜策略。

简要算法

算法分为两个步骤：

1. 打表，暴力算出所有可能的 24 点情况，这个步骤大概需要 0.1 s

2. 博弈，暴力搜索所有情况，按照比赛时使用的数据，这个步骤大约需要 0.1 s

参考程序

这个版本的参考程序目前是 192 中已提交中最快的：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
bitset<65536> v24;
inline double binop(double a, double b, int op) {
    switch(op) {
    case 0: return a + b;
    case 1: return a - b;
    case 2: return b - a;
    case 3: return a * b;
    case 4: return a / b;
    case 5: default: return b / a;
    }
}
inline bool t24(double a) {
    return a > 23.99999 and a < 24.00001;
}
void i24() {
    int a[5] = { 1 };
    int op[3];
#define FORA(i) for (a[i] = 1; a[i] < 11; a[i]++)
#define FOROP(i) for (op[i] = 0; op[i] < 6; op[i]++)
#define OP binop
    FORA(1) FORA(2) FORA(3) FORA(4) {
        int b[4] = {a[1], a[2], a[3], a[4]};
        sort(b, b + 4);
        int v = (b[0] + (b[1] << 4) + (b[2] << 8) + (b[3] << 12));
        if (v24.test(v)) continue;
        bool success = false;
        FOROP(0) FOROP(1) FOROP(2) 
            if  (
                t24(OP(OP(OP(a[1], a[2], op[0]), a[3], op[1]), a[4], op[2]))
                || t24(OP(OP(a[1], a[2], op[0]), OP(a[3], a[4], op[1]), op[2]))
                ) {
                success = true;
                goto i24_setbit;
            }
i24_setbit:
        if (success) v24.set(v);
    }
#undef FORA
#undef FOROP
}
struct Card {
    int n;
    char c;
    void read() {
        scanf("%d %c", &n, &c);
    }
};
struct State {
    Card d[4], p[2][4];
    const bool test() const {
        int ihc[4] = { d[0].n, d[1].n, d[2].n, d[3].n };
        sort(ihc, ihc + 4);
        int v = (ihc[0] + (ihc[1] << 4) + (ihc[2] << 8) + (ihc[3] << 12));
        return (v24.test(v) != 0);
    }
} state;
int k,m;
// return true if Sima Yi wins
bool gao(int who = 0, bool first_round = false) {
    // set win to 24 judge from desktop currently
    bool win = state.test(); 
    if (who) {
        // Zhang Jiao's turn, he wins if there is one way to win
        if (!win) return win;
        for (int i = 0; i < m; i++) {
            Card card = state.p[who][i];
            if (card.c == 'b') {
                // can use that card to swap a card in desktop
                for (int j = 0; j < 4; j++) {
                    // backup card at desktop and swap
                    Card card_backup = state.d[j];
                    state.d[j] = card;
                    state.p[who][i] = card_backup;
                    if (!gao(who ^ 1)) {
                    state.p[who][i] = card;
                    state.d[j] = card_backup;
                        return win = false;
                    }
                    // resume cards
                    state.p[who][i] = card;
                    state.d[j] = card_backup;
                }
            }
        }
    } else {
        if (first_round) win = false;
        if (win) return win;
        // Si Mayi's turn, he will win if there is just one way to win
        for (int i = 0; i < k; i++) {
            Card card = state.p[who][i];
            if (card.n > 0) {
                state.p[who][i].n = -1;
                // use that card to replace a card in desktop
                for (int j = 0; j < 4; j++) {
                    Card card_backup = state.d[j];
                    state.d[j] = card;
                    if (gao(who ^ 1)) {
                        state.d[j] = card_backup;
                        state.p[who][i] = card;
                        return win = true; 
                    }
                    state.d[j] = card_backup;
                }
                // resume that card
                state.p[who][i] = card;
            }
        }
    }
    return win;
}
int main(int argc, char const* argv[])
{
    // init 24, 0.13 s
    i24();
    int tc;
    scanf("%d", &tc);
    for (int ti = 0; ti < tc; ti++) {
        for (int i = 0; i < 4; i++)  state.d[i].read();
        scanf("%d%d", &k, &m);
        for (int ki = 0; ki < k; ki++) state.p[0][ki].read();
        for (int mi = 0; mi < m; mi++) state.p[1][mi].read();
        if (gao(0, true) || gao(1)) puts("Sima Yi Wins!");
        else puts("Zhang Jiao Wins!");
    }
    return 0;
}