codeforces每日一练。 题意: 有n张卡片,卡片上的数字就是分数,比如说甲乙两人抽卡,三局两胜,一局得分高的胜,求在甲赢了两局的情况下乙赢了第三局且总分比甲高的概率。 思路: 数据1e3,很明显的On^2算法,所以考虑暴力。 把分数数组排序,然后用cnt每轮可能出现的情况个数,cnt1统计分数差出现次数,cnt2统计甲前两局领先乙的总分方案数。 很明显,排序后的a[n]为最大得分,所以可以遍历1~a[n],两层循环统计甲前两局领先乙的总分方案数,cnt2[i+j]=cnt1[i]*cnt1[j] 。 最后也是两层循环,枚举分差,每对可能出现的分差对答案的贡献为: cnt1[i] * c