当前位置：首页 > news >正文

UVa 542 France ‘98

news 2026/6/21 9:16:26

题目描述

\texttt{}题目要求计算161616支球队在世界杯淘汰赛中的夺冠概率。淘汰赛赛程固定（见题图），每场比赛的胜率由16×1616 \times 1616×16的概率矩阵给出（pijp_{ij}pij表示球队iii战胜球队jjj的概率，且pij+pji=100p_{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 p=8.54% Chile p=1.60% Nigeria p=8.06% Denmark p=2.79% Holland p=4.51% Yugoslavia p=7.50% Argentina p=8.38% England p=1.56% Italy p=9.05% Norway p=3.23% France p=13.72% Paraguay p=3.09% Germany p=13.79% Mexico p=3.11% Romania p=5.53% Croatia p=5.53%

题目分析

本题的核心是动态规划计算每支球队在每轮比赛中晋级的概率。

赛程结构

淘汰赛共有444轮：

第111轮（161616进888）：相邻两支球队比赛。
第222轮（888进444）：相邻两组胜者比赛。
第333轮（半决赛）：相邻四组胜者比赛。
第444轮（决赛）：相邻八组胜者比赛。

动态规划定义

设win[i][r]\textit{win}[i][r]win[i][r]表示球队iii进入第rrr轮（即赢下前rrr轮比赛）的概率。r=0r=0r=0时，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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;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(inti=0;i<16;i++)cin>>names[i];for(inti=0;i<16;i++){for(intj=0;j<16;j++)cin>>possibility[i][j];win[i][0]=100.0;for(intj=1;j<=4;j++)win[i][j]=0.0;}intgroup=2,last_group=1;for(inti=1;i<=4;i++){for(intj=0;j<16;j++){for(intk=0;k<16;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_group=group;group*=2;}for(inti=0;i<16;i++){cout<<setw(10)<<left<<names[i];cout<<" p=";cout<<fixed<<setprecision(2)<<win[i][4];cout<<"%\n";}return0;}