程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> CodeForces 482C Game with Strings

CodeForces 482C Game with Strings

編輯：C++入門知識

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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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;
}