意甲冠军：
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\n", res / n);
return 0;
}
版权声明：本文博客原创文章。博客，未经同意，不得转载。