Caddi Programming Contest 2021(AtCoder Beginner Contest 193)-D - Poker-题解

---

题目大意

有1~9的牌各K张，每人分5张。
得分规则是$\sum _{i=1}^{9}i\times 10^{c_i}$，其中$C_i$是这个人有牌$i$的张数。
当每人发了4张牌时，问第一个人获胜的概率。

---

解题思路

把$\sum _{i=1}^{9}i\times 10^{c_i}$理解了一切就好说了。
这句话的意思是假如有4张2，那么就获得2 * 10000（4个0）分。1张3，获得3 * 10（1个0）分。0张5，就获得5 * 1（0个0）分。

我们可以把每个人获得牌的情况枚举，计算获胜的情况占总情况的比例。
第一个人最后一张是1，第二个人最后一张是2，共9种情况；
第一个人最后一张是5，第二个人最后一张是6，共18种情况；
… …（纯属虚构）
需枚举第一个人1 ~ 9，第二个人1 ~ 9，共81次。

假如有牌堆里还剩下3张2，9张1，考虑第一个人得到2，第二个人得到1时，第一个人共有$A_3^1=3$种情况，第二个人共有$A_9^1=9$种情况，一共有$3\ast 9=27$种情况。
假如有牌堆里还剩下9张1，考虑第一个人得到1，第二个人也得到1时，一共有$A_9^2=72$种情况。
而不管怎样，总情况就是$A_{剩余张数}^2$。

---

AC代码

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;

ll getScore(ll s[]) //计算总得分
{
    ll ans=0;
    for(ll i=1;i<10;i++)
    {
        ans+=i*pow(10,s[i]);
    }
    return ans;
}
int main()
{
    ll k;
    cin >> k; 
    char s[10], t[10];
    cin >> s >> t;
    ll shengyu[10] = {0}; //shengyu[i]表示i还剩多少张
    for (ll i = 1; i < 10; i++)
        shengyu[i] = k; //没有发牌时1~9都各剩k张
    ll suma[10] = {0}; //s中有每种牌各多少
    ll sumb[10] = {0}; //t中有每种牌各多少
    for (ll i = 0; i < 4; i++) //已经发下来的前4张
    {
        shengyu[s[i] - '0']--; //第一个人起到了s[i]，s[i]的剩余张数减1
        shengyu[t[i] - '0']--; //第一个人起到了t[i]，t[i]的剩余张数减1
        suma[s[i]-'0']++;//第一个人起到了s[i]，第一个人的s[i]的张数加1
        sumb[t[i]-'0']++;//第一个人起到了t[i]，第一个人的t[i]的张数加1
    }
    ll canWin=0; //所有可以获胜的情况
    for (ll i = 1; i <= 9; i++) //第一个人起到了i
    {
        for (ll j = 1; j <= 9; j++) //第二个人起到了j
        {
            bool sfbx=false; //这种情况是否不行（当剩余牌没有i和j时，这种情况不行）
            if(shengyu[i]<=0)sfbx=true; //没i了
            if(shengyu[j]<=0)sfbx=true; //没j了
            if(i==j && shengyu[i]<=1)sfbx=true; //没有两张i
            suma[i]++; //第一个人起到了i
            sumb[j]++; //第二个人起到了j
            if(!sfbx) //不是不行
            {
                ll sa=getScore(suma); //第一个人的得分
                ll sb=getScore(sumb); //第二个人的得分
                if(sa>sb) //第一个人获胜
                {
                    if(i==j) //两人最后一张牌相同
                        canWin += shengyu[i] * (shengyu[i]-  1);
                    else
                        canWin += shengyu[i] * shengyu[j];
                }
            }
            suma[i]--; //这种情况考虑结束，放回最后一张牌
            sumb[j]--;
        }
    }
    ll shengyuAll = k*9-8; //所有剩余的牌
    ll canAll = shengyuAll*(shengyuAll-1); //所有可能的情况（对应A shengyuAll 2）
    double ans = 1. * canWin / canAll;
    printf("%.15lf\n", ans);
    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
59
60
61
62
63
64
65
66
67
68