UVa 561 Jackpot
题目描述
题目要求计算老虎机的中奖率（期望收益）。老虎机有三个滚轮，每个滚轮上有若干符号（用大写字母表示）。中奖规则如下：
- 中间一行：若三个滚轮显示的符号相同，奖励101010个硬币。
- 上方一行和下方一行：若三个滚轮显示的符号相同，奖励555个硬币。
- 对角线（左上到右下、左下到右上）：若三个滚轮显示的符号相同，奖励777个硬币。
所有中奖条件独立计算，即同一个符号可以同时满足多个条件。期望收益为所有可能组合的平均奖励。
输入格式
第一行一个整数sss，表示老虎机的数量。每个老虎机的输入包含：
- 第一行三个整数xxx、yyy、zzz（3≤x,y,z≤2003 \le x, y, z \le 2003≤x,y,z≤200），分别表示三个滚轮的符号数。
- 三行字符串，分别表示三个滚轮上的符号（按顺序排列）。
输出格式
对于每个老虎机，输出一行期望收益，保留四位小数。
样例
输入
2 3 4 6 AAB BABA BBAAAB 12 15 18 CCCCCCCCCCCC CCCCCCCCCCCCCCC CCCCCCCCCCCCCCCCCC输出
8.5000 34.0000题目分析
本题的核心是计算每个符号在三个滚轮上出现的概率，然后乘以对应的奖励。
概率计算
- 每个滚轮独立旋转，每个符号出现的概率等于该符号在该滚轮上的出现次数除以滚轮总符号数。
- 对于给定的符号，三个滚轮同时显示该符号的概率为p1×p2×p3p_1 \times p_2 \times p_3p1×p2×p3。
- 中奖线共有555条，每条线奖励不同。实际上，每条线中奖时奖励固定，与符号无关。因此，总期望收益为：
期望=∑symbol概率×(中间行10+上下行5+对角线7) \text{期望} = \sum_{symbol} \text{概率} \times (\text{中间行}10 + \text{上下行}5 + \text{对角线}7)期望=symbol∑概率×(中间行10+上下行5+对角线7)
但上下行各有111条，对角线有222条，所以每条线的奖励累加为10+5×2+7×2=3410 + 5 \times 2 + 7 \times 2 = 3410+5×2+7×2=34。
因此，期望收益 =∑i=126(count1[i]x×count2[i]y×count3[i]z)×34\sum_{i=1}^{26} \left( \frac{count_1[i]}{x} \times \frac{count_2[i]}{y} \times \frac{count_3[i]}{z} \right) \times 34∑i=126(xcount1[i]×ycount2[i]×zcount3[i])×34。
实际上，每行和对角线出现相同字母的概率是一样的，也就是说，假设一行中奖的概率为xxx，对角线中奖的概率为yyy，则有x=yx=yx=y。则期望收益等于：
x×10+x×5+x×5+y×7+y×7=x×34 x \times 10 + x \times 5 + x \times 5 + y \times 7 + y \times 7 = x \times 34x×10+x×5+x×5+y×7+y×7=x×34
在计算时，获取每种字母的中奖概率xxx，乘以期望收益，最后求和即可。
复杂度分析
每个老虎机O(26)O(26)O(26)，可接受。
代码实现
// Jackpot// UVa ID: 561// Verdict: Accepted// Submission Date: 2017-05-12// UVa Run Time: 0.000s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases=0,x,y,z;string wheel1,wheel2,wheel3;cin>>cases;for(intc=1;c<=cases;c++){cin>>x>>y>>z;cin>>wheel1>>wheel2>>wheel3;intcount1[26]={0},count2[26]={0},count3[26]={0};for(inti=0;i<x;i++)count1[wheel1[i]-'A']++;for(inti=0;i<y;i++)count2[wheel2[i]-'A']++;for(inti=0;i<z;i++)count3[wheel3[i]-'A']++;doubleaverage=0.0;for(inti=0;i<26;i++){doublerate=1.0;rate*=(double)(count1[i])/(double)(x);rate*=(double)(count2[i])/(double)(y);rate*=(double)(count3[i])/(double)(z);average+=rate*34.0;}cout<<fixed<<setprecision(4)<<average<<'\n';}return0;}