AtCoder Beginner Contest 193(补题)

D - Poker

题意：

一共有$9\ast K$张卡片，每个卡片编号从1——9，每个编号的卡片有K，张，现在高桥前四张卡片已经知道，第5张卡片位置，青木也是如此，对于每个人的分数计算公式在下面，$c_i$是此人拥有编号为$i$的数量，现在问高桥获胜的概率。

思路：

直接暴力枚举高桥第五张牌的所有情况，青木也是如此，记剩下卡牌数位$cnt$,那总情况数就是$cnt\ast (cnt-1)$，也就是计算概率时的分母。分子就是高桥赢的情况数，从1——9所有数都枚举一遍，按照上面公式算出两人分数，高桥赢了的话，记当前枚举的编号为$i$的卡牌，青木是$j$，那么情况数就是$cnt[i]\ast cnt[j](i!=j)$$(cnt[i])\ast (cnt[i]-1)$$（i==j情况下）$

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define ll long long
int k;
string S, T;
int vis1[10], vis2[10], vis[10];
ll qmi(int a, int k) {
    ll res = 1;
    while (k) {
        if (k & 1) res = (ll)res * a;
        k >>= 1;
        a = (ll)a * a;
    }
    return res;
}

ll Sum(string k, int x, int a[]) {
    ll sum = 0;
    for (int i = 1; i < 10; i++) {
        if (i == x) {
            sum = (ll)sum + (ll)i * qmi(10, a[i] + 1);
        } else
            sum = (ll)sum + (ll)i * qmi(10, a[i]);
    }
    return sum;
}
int main() {
    scanf("%d", &k);
    cin >> S >> T;
    for (int i = 0; i < 4; i++) {
        vis1[S[i] - '0']++;
        vis2[T[i] - '0']++;
        vis[S[i] - '0']++;
        vis[T[i] - '0']++;
    }

    double res = 0;
    double q = (double)(9 * k - 8) * (9 * k - 8 - 1);
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            if (i != j) {
                if (vis[i] > k - 1 || vis[j] > k - 1) continue;
            } else {
                if (vis[i] > k - 2) continue;
            }
            if (Sum(S, i, vis1) > Sum(T, j, vis2)) {
                if (i == j)
                    res = res + (double)(k - vis[i]) * (k - vis[i] - 1);
                else
                    res = res + (double)(k - vis[i]) * (k - vis[j]);
            }
        }
    }

    printf("%.8lf\n", 1.0 * res / q);
    return 0;
}
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

To be continued
如果你有任何建议或者批评和补充，请留言指出，不胜感激