意甲冠军：
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; }
版权声明：本文博客原创文章。博客，未经同意，不得转载。
转载于:https://www.cnblogs.com/bhlsheji/p/4620554.html
相关资源：数据结构—成绩单生成器