D3T3游戏题解

常规
,
1

D3T3游戏

题目

题目大意

给定一个$\left [0, n - 1 \right ] $的整数随机数生成器和两个长度是m的n进制数

A和B两个人轮流获得一个随机数，并且填入自己那个m位n进制数中的某个地方。最后数字大的人赢。

求第一个人的胜率，保留六位小数。

输入

有T个测试样例，每次输入n, m

输出

T行，每行一个实数（保留六位小数）

数据范围

2\le n \le 10
1 \le m \le10
满足$(n+1)^m \le 3000$

大致思路

博弈论的题目，考虑A的策略。对于每一个位子，得到的数字肯定写在胜率最大的地方。B则相反。我们可以使用记忆化搜索的方法。考虑f[i][j]表示A的数字大小为i, B的数字大小为j，存储的是胜率。每次搜索比较此时的胜负。

对于可行性的讨论。关注到$(n+1)^m \le 3000$说明f数组完全开的下。而状态的总数量是$(n+1)^{2m} \le 9000000$在时间上也没有问题

代码注意

  • 对于浮点类型的数字建议使用循环赋值的方法，memset()使用将会得到无法所要的结果，因为浮点类存储方式不同
  • 对于check()函数， 平局不可以返回胜利
  • 在随机数字时生成$\left [ 1, n\right]$大小的数字，可以保证0与00时不同的情况。对应的，进制就需要乘上n+1了

CODE

#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cstring>
#define lfor(i, x, y) for (int i = (x); i <= (y); ++ i)
#define llfor(i, x, y) for (int i = (x); i < (y); ++ i)
#define rfor(i, x, y) for (int i = (x); i >= (y); -- i)
#define rlfor(i, x, y) for (int i = (x); i > (y); -- i)
#define For(i, p) for(int i = head[p]; i; i = nxt[i])
using namespace std;

typedef long double ld;
const int N = 21;
const int M = 3010;
ld f[M][M];
int p[N], cx, cy;
int ax[N], ay[N];
int n, m;

int check() {
	lfor(i, 0, m - 1) {
		if (!(ax[i] && ay[i])) return 0;
		if (ax[i] < ay[i]) return -1;
		if (ax[i] > ay[i]) return 1;
	}
	return -1;
}

ld dfs(int per) {
	if (f[cx][cy] != -1) return f[cx][cy];
	int res = check();
	ld ans = 0;
	if (res != 0) return (res == 1);
	if (per) {
		lfor(i, 1, n) {
			ld mp = 0;
			lfor(j, 0, m - 1) if(!ax[j]) {
				ax[j] = i, cx += p[j] * i;
				mp = max(mp, dfs(per ^ 1));
				ax[j] = 0, cx -= p[j] * i;
			}
			ans += mp;
		}
		return f[cx][cy] = ans / n;
	}
	lfor(i, 1, n) {
		ld mp = 1;
		lfor(j, 0, m - 1) if (!ay[j]) {
			ay[j] = i, cy += p[j] * i;
			mp = min(mp, dfs(per ^ 1));
			ay[j] = 0, cy -= p[j] * i; 
		}
		ans += mp;
	}
	return f[cx][cy] = ans / n;
}

void work() {
	cin >> m >> n;
	p[0] = 1; cx = cy = 0;
	lfor(i, 1, m) p[i] = p[i - 1] * (n + 1);
	int maxn = 0; lfor(i, 0, m - 1) maxn += p[i] * n;
	lfor(i, 0, m - 1) ax[i] = ay[i] = 0;
	lfor(i, 0, maxn) lfor(j, 0, maxn) f[i][j] = -1.0;
	printf("%.6Lf\n",dfs(1));
}

int main() {
    int T; cin >> T;
    while (T --) work();
	return 0;
}