题目描述\texttt{}题目要求计算161616支球队在世界杯淘汰赛中的夺冠概率。淘汰赛赛程固定见题图每场比赛的胜率由16×1616 \times 1616×16的概率矩阵给出pijp_{ij}pij​表示球队iii战胜球队jjj的概率且pijpji100p_{ij} p_{ji} 100pij​pji​100。输出每支球队的夺冠概率保留两位小数。输入格式输入只有一组测试用例。前161616行是球队名称按赛程图中的顺序。接下来是一个16×1616 \times 1616×16的整数矩阵pijp_{ij}pij​表示球队iii战胜球队jjj的概率百分比。输出格式输出161616行每行格式为球队名称左对齐宽度101010、p、夺冠概率保留两位小数、%。样例输入Brazil Chile Nigeria Denmark Holland Yugoslavia Argentina England Italy Norway France Paraguay Germany Mexico Romania Croatia 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 40 55 40 50 45 40 40 55 35 45 30 45 30 45 40 40 45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35 55 70 55 65 60 55 55 70 50 60 45 60 45 60 55 55 45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45 60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60 45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45 60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60 45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50输出Brazil p8.54% Chile p1.60% Nigeria p8.06% Denmark p2.79% Holland p4.51% Yugoslavia p7.50% Argentina p8.38% England p1.56% Italy p9.05% Norway p3.23% France p13.72% Paraguay p3.09% Germany p13.79% Mexico p3.11% Romania p5.53% Croatia p5.53%题目分析本题的核心是动态规划计算每支球队在每轮比赛中晋级的概率。赛程结构淘汰赛共有444轮第111轮161616进888相邻两支球队比赛。第222轮888进444相邻两组胜者比赛。第333轮半决赛相邻四组胜者比赛。第444轮决赛相邻八组胜者比赛。动态规划定义设win[i][r]\textit{win}[i][r]win[i][r]表示球队iii进入第rrr轮即赢下前rrr轮比赛的概率。r0r0r0时win[i][0]1\textit{win}[i][0] 1win[i][0]1初始即存在。对于r≥1r \ge 1r≥1球队iii进入第rrr轮的概率为win[i][r]win[i][r−1]×∑j∈可能的对手win[j][r−1]×pi,j/100 \textit{win}[i][r] \textit{win}[i][r-1] \times \sum_{j \in \text{可能的对手}} \textit{win}[j][r-1] \times p_{i,j} / 100win[i][r]win[i][r−1]×j∈可能的对手∑​win[j][r−1]×pi,j​/100其中“可能的对手”是指与iii在同一组按赛程分组且尚未相遇过的球队。具体分组规则为第111轮相邻两支球队为一组第222轮相邻两组共444支球队为一组但iii只可能与另一组中的球队比赛依此类推。实现方法使用分组大小为2r2^{r}2r的块iii所在块中与iii不在同一子块大小为2r−12^{r-1}2r−1的球队即为可能的对手。复杂度分析161616支球队444轮每轮计算O(162)O(16^2)O(162)可接受。代码实现// France 98// UVa ID: 542// Verdict: Accepted// Submission Date: 2016-09-24// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string names[16];doublepossibility[16][16]{0},win[16][5]{0};for(inti0;i16;i)cinnames[i];for(inti0;i16;i){for(intj0;j16;j)cinpossibility[i][j];win[i][0]100.0;for(intj1;j4;j)win[i][j]0.0;}intgroup2,last_group1;for(inti1;i4;i){for(intj0;j16;j){for(intk0;k16;k)if(((j/group)(k/group))((j/last_group)!(k/last_group)))win[j][i]win[k][i-1]*possibility[j][k]/10000.0;win[j][i]*win[j][i-1];}last_groupgroup;group*2;}for(inti0;i16;i){coutsetw(10)leftnames[i];cout p;coutfixedsetprecision(2)win[i][4];cout%\n;}return0;}