CF1765C
2023-04-07 22:08:31 7 举报
AI智能生成
CF1765C
作者其他创作
大纲/内容
桌面上有一堆牌,牌有n种,每种有4个花色
每次从桌上随机抽一张牌直至抽完,抽出来的卡牌序列会有(4n)!种
如果之前抽卡次数不足k次,则根据过去所有抽卡的结果进行判断
固定猜测出现次数最少的花色
给定常数k,每次抽卡时会根据之前k次抽卡的结果猜下一次抽卡的花色
阅读题目
根据期望线性性,只需求出每次猜测正确的概率并求和即可
考虑当前猜测是根据前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的答案加起来就是最终结果
进行分析
令f[i][j][k]表示放了前i个颜色,当前长度为j,最小值为k的方案数
结合求解
Codeforces 1765C
0 条评论
回复 删除
下一页