Codeforces Round 275 E.Game With Strings @ Wings            分类 ACM
发布于 星期四, 二月 4 日, 2021 年
更新于 星期二, 七月 20 日, 2021 年

题目

题意

$n$ 个长为 $m$ 的不同字符串, 等概率地藏起来一个字符串, 然后游戏者来猜藏起来的串是什么. 每一步游戏者等概率地询问该字符串的某个位置的字符是什么. 不断地知道该字符串的一些位置的字符后, 游戏者就可以确定藏起来的串是什么, 题目要求游戏者的期望步数.

$1 \le n \le 50, 1 \le m \le 20$

题解

这个步数期望的贡献转化没见过, 记下来.

由于期望的线性性质, 我们可以先求猜出某一个的期望步数. 这样乘以 $\frac{1}{n}$ 就是所有的期望步数了.

然后考虑如何求猜出一个串的期望步数.这里转化一下贡献, 把步数拆开, 即变为 $$E' = \sum_{s \in ALL, |s| = 1}P(s) \cdot 1(\text{走第一步}) + \sum_{s \in ALL, |s| = 2}P(s) \cdot 1(\text{走第二步}) + \dots$$

其中$ALL$是询问集合全集, 即每个位置都询问.

可以发现, 某个字符串对答案有贡献, 当且仅当走第 $k$ 步不能确认.

再根据线性性质, 把询问$s$不能确认的字符串个数加进去, 就有 $$E = \sum_{k=0}^{m} \sum_{s \in ALL, |s| = k}P(s) \cdot \frac{\text{#不能确定的字符串}}{n}$$

(这里故意用集合元素个数把他拆开来了, 对于上面的$E'$的做法, 两个$\Sigma$其实就是在枚举所有子集)

假设某一次询问的位置集合是 $s$, 无论我用什么顺序走, 只要最后走出来的集合是 $s$, 不能确定的字符串个数是一样的, 顺序无关紧要, 于是有 $$P(s) = \frac{1}{\binom{m}{|s|}}$$ 不能确定的字符串很容易理解, 就是当前询问集合位置都相同的字符串个数.

所以我们需要枚举询问集合, 求出这个询问集合中每个位置都相同的字符串个数.

很显然状压dp.

只不过dp值不是个数, 而是不能确认的字符串集合.

个数的话无法转移, 所以要用一个能够转移的dp值 —— 集合, 然后通过集合求个数即可.

先通过枚举字符串对, 把两个字符串相等的位置拿出来, 把这两个字符串加入到dp值集合中.

得到的这些$dp(s)$值集合的所有元素直接丢到$s$的子集即可, 因为$s$的子集也一定不能确定$dp(s)$.

复杂度$O(n^2 m + 2^m m)$

代码

cf交LD挂了

const int MAXN = 55;
const int MAXM = (1<<20) + 1;

LL dp[MAXM], C[MAXN][MAXN];
int n, m;
char a[MAXN][MAXN];
double ans = 0;

int count(LL x) {
	int res = 0;
	while (x)
		x &= (x-1), res++;
	return res;
}

void init() {
	for(int i = 0; i <= m; i++)
       for(int j = C[i][0] = 1; j <= i; j++)
           C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%s", a[i]);
	m = strlen(a[0]);
	init();
	for (LL i = 0; i < n; i++)
		for (LL j = 0; j < i; j++) {
			int same_bit = 0;
			for (int k = 0; k < m; k++)
				if (a[i][k] == a[j][k])
					same_bit |= 1 << k;
			dp[same_bit] |= (1ll << i) | (1ll << j);
		}
	for (int s = (1 << m) - 1; ~s; s--)
		for (int i = 0; i < m; i++)
			if ((1 << i) & s)
				dp[s ^ (1 << i)] |= dp[s];
	for (int s = 0; s < (1<<m); s++)
		ans += (double)count(dp[s]) / n / C[m][count(s)];
	printf("%.10lf\n", ans);
	return 0;
}
留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球
  • 三阶速拧20s

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch