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

题面

分析

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

代码

#include 

#define int long long

using 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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130