2022 icpc 沈阳站 L. Tavern Chess -dfs大模拟

本文主要是介绍2022 icpc 沈阳站 L. Tavern Chess -dfs大模拟，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

分析

大模拟，范围很小，可以直接用dfs进行模拟，唯一的坑就是可能误以为只需要暴搜统计最后的赢得次数、输的次数以及平局得次数最后再去算概率，但是这样是不对的，假如一种情况是进行到第5轮结束，结果为赢，另一种情况是第3种情况结束，结果也是赢，那么这样按照统计次数来算就是2，但是如果按照概率来算这两种情况的概率是不一样的，按照次数算的时候是同等概率的，所以会出现错误。

代码

#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 17;int n, m;
int a[N];
int b[N];
int cnt1[N], cnt2[N];
int aa[N], bb[N];
double win, lose, t;
int sum1, sum2, sum3;void dfs(int u, double p) {int flag0 = 0, flag1 = 0;for(int i = 0; i < n; i ++) {if(aa[i] > 0) {flag0 = 1;break;}}for(int i = 0; i < m; i ++) {if(bb[i] > 0) {flag1 = 1;break;}}if(flag0 && !flag1) {win += p;sum1 ++;return ;}else if(!flag0 && flag1) {lose += p;sum2 ++;return ;}else if(!flag0 && !flag1) {t += p;sum3 ++;return ;}if(u == 0) {int idx = -1, minn = 1e9;for(int i = 0; i < n; i ++) {if(aa[i] <= 0) continue;if(minn > cnt1[i]) {minn = cnt1[i];idx = i;}}cnt1[idx] ++;int cnt = 0;for(int i = 0; i < m; i ++) {if(bb[i] <= 0) continue;cnt ++;}double sum = 1.0 / (double)cnt;// cout << sum << endl;for(int i = 0; i < m; i ++) {if(bb[i] <= 0) continue;int x = a[idx];int y = b[i];aa[idx] -= y;bb[i] -= x;dfs(u ^ 1, p * sum);aa[idx] += y;bb[i] += x;}cnt1[idx] --;}else {int idx = -1, minn = 1e9;for(int i = 0; i < m; i ++) {if(bb[i] <= 0) continue;if(minn > cnt2[i]) {minn = cnt2[i];idx = i;}}int cnt = 0;cnt2[idx] ++;for(int i = 0; i < n; i ++) {if(aa[i] <= 0) continue;cnt ++;}double sum = 1.0 / (double)cnt;///cout << sum << endl;for(int i = 0; i < n; i ++) {if(aa[i] <= 0) continue;int x = a[i];int y = b[idx];bb[idx] -= x;aa[i] -= y;dfs(u ^ 1, p * sum);bb[idx] += x;aa[i] += y;}cnt2[idx] --;}
}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;for(int i = 0; i < n; i ++) {cin >> a[i];aa[i] = a[i];}for(int i = 0; i < m; i ++) {cin >> b[i];bb[i] = b[i];}if(n == m) {dfs(0, 0.5);dfs(1, 0.5);}else if(n > m) {dfs(0, 1.0);}else {dfs(1, 1.0);}printf("%.9lf\n%.9lf\n%.9lf\n", win, lose, t);
}