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!
结合求解
0 条评论
下一页
