题解：AT_abc392_d [ABC392D] Doubles

FlowerAccepted · 2025-02-14 10:39:13 · 题解

解题思路

记最大点数为 MAXA。

注意到一个 dice 可能有若干个相同的面，所以可以开一个大小 MAXN \times MAXA 的桶 qwq，令 qwq_{i, j}（1 \le i \le N，1 \le j \le MAXA）记录第 i 个 dice 有多少个数为 j 的面。

每次取 dice i，dice j（1 \le i, j \le N），枚举 k（1 \le k \le MAXA），将目前概率加上 \large{\frac{qwq_{i, k} \times qwq_{j, k}}{K_i \times K_j}}，分子表示这个点数能组合出多少种一样的点数 k 的组合，分母表示这两个 dice 一共能组合出多少种点数组合。枚举完 k 将答案与目前概率取最大值赋给新的答案即可。

注意精度喵～要先除再乘开 long double 呦！要 printf("%.15f")呦！不然 dice 们就会给你一个 35 倍暴击呦！（我试过先乘再除，会 \color{gold}\text{WA} 一个点，此乃 \text{XCPC} 赛制之最绝望）

代码呈现

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring> // aple clang 专属
using namespace std;

int a[105], qwq[105][100005]; // 开大防越界

int main() {
    int n, x, maxx = 0; // MAXA
    long double maxpos = 0, pos; // 答案、目前概率
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        for (int j = 1; j <= a[i]; j ++) {
            cin >> x;
            qwq[i][x] ++; // 桶计数
            maxx = max(maxx, x); // 最大点数
        }
    }
    for (int i = 1; i < n; i ++) {
        for (int j = i + 1; j <= n; j ++) {
            pos = 0;
            for (int k = 1; k <= maxx; k ++) {
                pos += ((long double)qwq[i][k] / a[i]) * ((long double)qwq[j][k] / a[j]); // 十天 AT 一场空，不开 ld 先乘见祖宗！
            }
            maxpos = max(maxpos, pos); // 取最大值
        }
    }
    printf("%.15Lf", maxpos); // 正常输出只能 5 或 6 位
    return 0;
}

复杂度分析

复杂度不小，是 O(N^2MAXA)。

后记 & 整活

好想要 U dice 啊！