题面
题目传送门 https://www.lydsy.com/JudgeOnline/problem.php?id=3191
解法
设 \(f_{i,j}\) 表示总共 \(i\) 个人, 第 \(j\) 个人最终获胜的概率
枚举当前选择的是哪一张卡, 那么就知道下一轮被淘汰的是谁了, 假设是 \(x\)
显然, 下一轮的庄家就是 \(x\) 的下一个人
如果 \(x=j\), 那么可以不用管这种情况
如果 \(x>j\), 那么 \(j\) 在下一轮的编号为 \(i-x+j\), 否则为 \(j-x\)
对应的两种情况转移一下即可
时间复杂度:\(O(n^2m)\)
代码
- #include <bits/stdc++.h>
- #define N 110
- using namespace std;
- int a[N];
- double f[N][N];
- int main() {
- int n, m; cin>> n>> m;
- for (int i = 1; i <= m; i++) cin>> a[i];
- f[1][1] = 1;
- for (int i = 2; i <= n; i++)
- for (int j = 1; j <= i; j++)
- for (int k = 1; k <= m; k++) {
- int x = a[k] % i ? a[k] % i : i;
- if (!x) x = n;
- if (x == j) continue;
- if (x> j) f[i][j] += f[i - 1][i - x + j] / m;
- else f[i][j] += f[i - 1][j - x] / m;
- }
- for (int i = 1; i <= n; i++)
- cout << fixed << setprecision(2) << f[n][i] * 100 << "%";
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2727913.html