Knockout Tournament Gym - 101623K（概率）

本文主要是介绍Knockout Tournament Gym - 101623K（概率），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
n个人比赛，要求每一轮两两比赛，每次比赛一个人晋级，晋级概率为a/(a+b)，a,b为两个人rating。
第一轮可以让一些人直接晋级，使得比赛树为完全二叉树，如图下。
在这里插入图片描述
求安排比赛方案使得第一个人最终获胜的概率最高。

思路：
除了第一个人直接按照rating排序，让第一个人尽量与rating小的人比赛，并且要求使得第一个人比赛场次尽可能少。之后就是一个模拟了。

这个模拟你可以递归模拟线段树建树过程，也可以直接补全最后一层成为完美二叉树然后再算出 $f [i] [j]$ ，表示 $i$ 这个人晋级到第 $j$ 轮的概率。

//tdm
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <iostream>
#include <string>
#include <cmath>using namespace std;typedef long long ll;const int maxn = 1e5 + 7;double f[33][maxn],a[maxn],b[maxn];int main() {int n;scanf("%d",&n);for(int i = 0;i < n;i++) scanf("%lf",&a[i]);int k = log2(n);int num = 1 << k;sort(a + 1,a + n);double flag = 1.0;if(num != n) {flag = 2.0;k++;num <<= 1;int cnt = 0;for(int i = 0;i < num - n;i++) {b[cnt++] = a[i];b[cnt++] = a[i];}for(int i = num - n;i < n;i++) {b[cnt++] = a[i];}for(int i = 0;i < num;i++) f[0][i] = 1.0;} else {for(int i = 0;i < num;i++) {f[0][i] = 1.0;b[i] = a[i];}}for(int i = 1;i <= k;i++) { //层次int len = 1 << i; // 长度for(int j = 0;j < num;j += len) { //起点for(int q = 0;q < len / 2;q++) { //左起点for(int p = len / 2;p < len;p++) { //右起点double p1 = b[j + q],p2 = b[j + p];f[i][j + q] += f[i - 1][j + p] * f[i - 1][j + q] * p1 / (p1 + p2);f[i][j + p] += f[i - 1][j + p] * f[i - 1][j + q] * p2 / (p1 + p2);}}}}printf("%.8f\n",f[k][0] * flag);return 0;
}