自动搬运

查看原文

来自洛谷，原作者为

	tuxiaobei **

搬运于2025-08-24 22:26:57，当前版本为作者最后更新于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;
}