首页  思维导图  详情



 



CF1765C

2023-04-07 22:08:31   7  举报





AI智能生成

CF1765C

算法

模板推荐

作者其他创作

大纲/内容

阅读题目

桌面上有一堆牌，牌有n种，每种有4个花色

每次从桌上随机抽一张牌直至抽完，抽出来的卡牌序列会有(4n)!种

给定常数k，每次抽卡时会根据之前k次抽卡的结果猜下一次抽卡的花色

如果之前抽卡次数不足k次，则根据过去所有抽卡的结果进行判断

固定猜测出现次数最少的花色

问期望猜测正确次数，n<=500,k<=4n

进行分析

根据期望线性性，只需求出每次猜测正确的概率并求和即可

考虑当前猜测是根据前K次的结果进行猜测，那么对答案有影响的只有卡牌序列中的这K个位置以及当前位置的结果

对每个K，考虑一个长度为K+1的卡牌序列，要求的就是有多少序列满足序列的最后一位与前K位中出现最少的花色相同

由于最小花色是哪一个对答案没有影响，于是联想到令g[i][j]表示长度为i且最少出现次数为j的序列个数

意识到由于每个花色的个数有上限，于是不能用组合数计算，考虑使用背包求解对应问题

当求出每个g[i][j]时，一个K的对应答案就是对g[K][j]*(n-j)求和后除以(sum g[K+1][j])的值。对每次猜测对应的K的答案加起来就是最终结果

对每个i,j，求出长度为i且最少出现次数为j的序列个数

背包求解,考虑一次将若干个同一花色的牌直接放入当前序列产生的贡献

令f[i][j][k]表示放了前i个颜色，当前长度为j，最小值为k的方案数

枚举下一个颜色放l个，可以转移到f[i+1][j+l][min(k,l)]

转移系数为C(n,l)*C(j+l,l)*l!

结合求解

 Collect

Get Started

 Collect

Get Started

 Collect

Get Started

C，数组

 Collect

Get Started

C1-1





0 条评论

下一页