2022 ICPC 沈阳 L(模拟 ， dfs)

Problem - L - Codeforces

大意：给出两支队伍 ， 交替发动攻击 ， 问两支队伍分别获胜和平局的概率。

一：先手规则：

两队轮流发动攻击(take turns) ，人数多的先手 ， 人数相同先手概率都是 50%。

Alice and Bob’s teams take turns to attack, and the team that has more minions takes the first attack. In case of a tie（平局）, it will be decided by a coin toss — 50% probability for Alice taking the first attack and the remaining 50% probability for Bob taking the first attack.

二：攻击规则

When a team takes the attack, the leftmost minion(仆从) taking the minimum number of attacks from the team attacks one of the alive minions from the other team uniformly at random, and then the other team takes the attack.

队伍中最靠左且攻击次数最少的仆从发动攻击 ， 等概率的攻击另一个队伍中活着的成员。

思路：由于 n 和 m 范围都很小 ， 深搜模拟即可。要注意的是

1. 决定谁先攻击的是攻击次数 ，而不是其他东西。

2. 对于概率的计算 ， 到达每个局面的概率都是不同的 ， 所以不能用次数去代替概率。

3. 对于深搜的写法来说 ， 一定要注意各个数组的回溯 ， 尤其是攻击次数数组的回溯 ， 这很重要。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int n , m;
int a[N] , b[N];//攻击力
int aa[N] , bb[N];//血量
int cnta[N] , cntb[N];//攻击次数
bool visa[N] , visb[N];//存活情况
int al , bl;
double sum1 , sum2 , sum3;// 奇数 a 走 偶数 b 走
void dfs(int x , double now){if(al == 0 && bl){ sum2 += now; return ; }if(al && bl == 0){ sum1 += now; return ; }if(al == 0 && bl == 0){ sum3 += now; return ; }int id = 0 , cnt = 9e18;if(x % 2 == 0){for(int i = 1 ; i <= m ; i ++){if(visb[i]) continue;if(cntb[i] < cnt){cnt = cntb[i];id = i;}}cntb[id] += 1;double alive = al;for(int i = 1 ; i <= n ; i ++){if(visa[i) continue;bb[id] -= a[i];aa[i]  -= b[id];if(bb[id] <= 0) visb[id] = 1 , bl -= 1;if(aa[i]  <= 0) visa[i]  = 1 , al -= 1;dfs(x + 1 , now / alive);bb[id] += a[i];aa[i]  += b[id];if(visb[id]) visb[id] = 0 , bl += 1;if(visa[i]) visa[i] = 0 , al += 1;}cntb[id] -= 1;//回溯攻击次数数组} else {for(int i = 1 ; i <= n ; i ++){if(visa[i]) continue;if(cnta[i] < cnt){cnt = cnta[i];id = i;}}cnta[id] += 1;double alive = bl；for(int i = 1 ; i <= m ; i ++){if(visb[i]) continue;aa[id] -= b[i];bb[i]  -= a[id];if(aa[id] <= 0) visa[id] = 1 , al -= 1;if(bb[i]  <= 0) visb[i]  = 1 , bl -= 1;dfs(x + 1 , now / alive);aa[id] += b[i];bb[i]  += a[id];if(visa[id]) visa[id] = 0 , al += 1;if(visb[i]) visb[i] = 0 , bl += 1;}cnta[id] -= 1;}
}signed main(){IOScout << fixed << setprecision(10);cin >> n >> m;for(int i = 1 ; i <= n ; i ++) cin >> a[i] , aa[i] = a[i];for(int i = 1 ; i <= m ; i ++) cin >> b[i] , bb[i] = b[i];al = n;bl = m;if(n == m){ dfs(1 , 0.5); dfs(0 , 0.5) ;}if(n > m) dfs(1 , 1.0);if(n < m) dfs(0 , 1.0);cout << sum1 << " " << sum2 << " " << sum3 << "\n";return 0;
}