小 B 的面包

tuxiaobei · 2020-12-13 12:38:03 · 题解

这里是出题人（

本题其实可以转化成经典的“井字棋”游戏，构造如下：

当然不知道也没有关系，数据规模这么小我们可以直接预处理搜索。

记录总局数和获胜局数，搜索到每一层，如果轮到自己选取，则取获胜概率最大的策略，否则将总局数和获胜局数求和。

搜索完成后，我们发现对于全部情况，先手获胜概率大于 99\%，后手获胜概率大于 88\% ，足以通过此题。

这道题也可以贪心，只要你熟悉井字棋即可。

搜索标程（很久以前写的，写得比较丑

#include <bits/stdc++.h>
#define maxn 12
using namespace std;
int Pow[maxn];
bool fg;

struct st {
    int a[maxn];
    int Hash() {
        int h = 0;
        for (int i = 1; i <= 9; i++) {
            h += a[i] * Pow[i - 1];
        }
        return h;
    }
    int win() {
        bool flag = true;
        for (int i = 1; i <= 9; i++) {
            if (!a[i]) flag = false;
            for (int j = 1; j <= 9; j++) {
                int k = 15 - i - j;
                if (a[i] == 0 || a[i] != a[j] || i == j || i == k || j == k || k < 1 || k > 9) continue;
                if (a[k] == a[i]) return a[i];
            }
        }
        if (flag) return 3;
        return 0;
    }
} now, s;

struct rec {
    int win, tot, chs;
    rec operator + (const rec& x)const {
        rec res;
        res.win = win + x.win;
        res.tot = tot + x.tot;
        return res;
    }
} f[40000][3];
int nowdfs;
void dfs(int key, st x, int pos)
{

    if (f[key][nowdfs].tot) return;
    int p = x.win();
    if (p) {
        f[key][nowdfs].tot = 1;
        if (p == 1) f[key][nowdfs].win = -1e5;
        else if (p == 2) f[key][nowdfs].win = 1;
        return;
    }
    double Max = -1e9;
    for (int i = 1; i <= 9; i++) {
        if (x.a[i]) continue;
        st v = x;
        v.a[i] = pos;
        int h = v.Hash();
        dfs(h, v, pos == 1 ? 2 : 1);
        if (pos == 1) f[key][nowdfs] = f[key][nowdfs] + f[h][nowdfs];
        else {
            if ((double)f[h][nowdfs].win / f[h][nowdfs].tot > Max) {
                Max = (double)f[h][nowdfs].win / f[h][nowdfs].tot;
                f[key][nowdfs] = f[h][nowdfs];
                f[key][nowdfs].chs = i;
            }
        }
    }
}

extern "C" void init()
{
    Pow[0] = 1;
    for (int i = 1; i <= 8; i++)
        Pow[i] = Pow[i - 1] * 3;
    nowdfs = 1;
    dfs(0, s, 1);
    nowdfs = 0;
    dfs(0, s, 2);
}

extern "C" void newgame(bool flag) { fg = flag; memset(now.a, false, sizeof(now.a)); }

extern "C" int choose(int x)   //x为选取的面包
{
    if (x != 0) now.a[x] = 1;
    int key = now.Hash();
    int p = f[key][fg].chs;
    now.a[p] = 2;
    return p;
}