CodeForces 482C Game with Strings

意甲冠军：

n一定长度m串隐藏的字符串相等的概率然后，你猜怎么着玩家隐藏的字符串的询问字符串的一个位置再不断的知道一些位置后游戏者就能够确定藏起来的串是什么问游戏者的期望步数

思路：

能够说是一道概率题也能够说是期望题总之感觉题目不错…

首先假设我们枚举藏起来的串是哪个（复杂度n）然后利用状压去dp维护猜某些位的状态的概率以及对于那个状态剩下哪些串是无法辨别的（复杂度m*2^m）那么复杂度为 O(nm2^m) 这样就会TLE

接着思考事实上问题不是出在状压的2^m上（它已经非常优秀了）既然不去掉状压那么辅助状态转移的m也扔不掉我们仅仅能想方法避免那个n 使复杂度达到 O(m2^m)

然后我们来确定方案：

我们用状压的二进制数表示m个位置有哪些位置已经被揭示了那么我们能够利用dp求出对于每一个状态的概率（或者称为从一位都不揭示到揭示到如今这样的状态的期望）那么对于如今这样的状态假设已经能够猜到藏起来的是哪个串那么我们就不须要再猜了否则至少要猜下一步那么这个“下一步”对于整个游戏期望步数的贡献就为dp[状态]*1

如今问题就在怎样推断这个状态是不是猜完了

事实上这个问题能够用dp打表出对于已经猜了一些位置后有哪些串是如今的状态分辨不出来的（代码中的f数组）

那么假设f为0 表示已经猜到了假设不为0则里面至少有2个1存在则对于当中的每一个1 假设藏起来的正是1相应的那个串则还须要1步那么这1步对答案的贡献就是刚才说的dp[]*1了

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<bitset>
using namespace std;
typedef long long LL;
#define N 55
#define M 25

int n, len;
char str[N][M];
LL f[(1 << 20) + 10], bin[N];
double ans[(1 << 20) + 10];
double res;

int main() {
	int i, j, k, c;
	bin[0] = 1;
	for (i = 1; i < N; i++)
		bin[i] = (bin[i - 1] << 1);
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%s", str[i]);
	len = strlen(str[1]);
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			if (i != j) {
				int same = 0;
				for (k = 0; k < len; k++) {
					if (str[i][k] == str[j][k])
						same |= bin[k];
				}
				f[same] |= bin[j];
			}
		}
	}
	for (i = bin[len] - 1; i >= 0; i--) {
		for (j = 0; j < len; j++) {
			if (i & bin[j]) {
				f[i ^ bin[j]] |= f[i];
			}
		}
	}
	ans[0] = 1;
	for (i = 0; i < bin[len]; i++) {
		for (c = j = 0; j < len; j++) {
			if (i & bin[j])
				c++;
		}
		for (j = 0; j < len; j++) {
			if (!(i & bin[j]))
				ans[i | bin[j]] += ans[i] / (len - c);
		}
		for (j = 0; j < n; j++) {
			if (f[i] & bin[j])
				res += ans[i];
		}
	}
	printf("%.10f
", res / n);
	return 0;
}