题解：AT_abc392_d [ABC392D] Doubles

yyycj · 2025-02-09 18:49:29 · 题解

题目传送门

题目简述

有 N 个骰子，第 i 个骰子有 K_{i} 个面，上面写着数字 A_{i,1} \sim A_{i,K_{i}} 求任意选择两个骰子能掷出一样的面的最大值。

主要思路

这题其实暴力的 O(N^{2}K) 是可以卡过的，并且如果用上快速读入等方法并不慢。开一个 cnt 二维数组，记录第 i 个骰子第 j 个数字出现了几次。然后遍历选两个骰子的每种情况，记录一个表示概率和的变量并设为 0，内部再对于每个 l \in [1,10^{5}]，计算两个骰子都能掷出 l 的概率，即第 i 个骰子出现 l 的概率乘第 j 个骰子出现 l 的概率，将这些概率相加，就是选第 i 个骰子和第 j 个骰子能掷出一样的面的概率。最后，将答案设为答案和概率和的最大值。

AC Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#ifdef ONLINE_JUDGE
#define getchar getchar_unlocked
#endif

#define OUT 0
#define endl '\n'
#define pc putchar
#define gc getchar
#define MAMBA return
typedef long long ll;
typedef long double db;
const int N = 100 + 10;
const int A = 1e5 + 10;
const int INF = 0x3f3f3f3f;
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repr(i, a, b) for (int i = a; i >= b; i--)
void print(string s) { size_t n = s.length(); for (size_t i = 0; i < n; i++)pc(s[i]); }
void print(ll x) { if (x < 0) { pc('-'); x = -x; }if (x > 9) { print(x / 10); }pc(char(x % 10 + 48)); }
void print(int x) { if (x < 0) { pc('-'); x = -x; }if (x > 9) { print(x / 10); }pc(char(x % 10 + 48)); }
inline char read_char() { char ch = getchar(); while (ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t') ch = getchar(); return ch; }
inline int read_int() { int f = 1, x = 0; char ch = gc(); while (!isdigit(ch)) { if (ch == '-')f = -1; ch = gc(); }while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = gc(); }return x * f; }int man();
inline ll read_ll() { int f = 1; ll x = 0; char ch = gc(); while (!isdigit(ch)) { if (ch == '-')f = -1; ch = gc(); }while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = gc(); }return x * f; }int main() { MAMBA man(); }
// ----------------------------

// ----------------------------
int k[N], cnt[N][A];
// ----------------------------

int man() {
    int n = read_int();
    rep(i, 1, n) {
        k[i] = read_int();
        rep(j, 1, k[i]) cnt[i][read_int()]++;
    }
    // ----------------------------
    db sum, ans = 0;
    rep(i, 1, n) {
        rep(j, i + 1, n) {
            sum = 0;
            rep(l, 1, 100000) {
                if (cnt[i][l] == 0 || cnt[j][l] == 0) continue;
                sum += (double)(cnt[i][l]) / k[i] * ((double)(cnt[j][l]) / k[j]);
            }
            ans = max(ans, sum);
        }
    }
    // ----------------------------
    printf("%.15Lf", ans);
    MAMBA OUT;
}
/*
                 .-~~~~~~~~~-._       _.-~~~~~~~~~-.
             __.'              ~.   .~              `.__
           .'//   A    C    之   \./  之    真    理  \`.
         .'//                     |                     \`.
       .'// .-~"""""""~~~~-._     |     _,-~~~~"""""""~-. \`.
     .'//.-"                 `-.  |  .-'                 "-.\`.
   .'//______.============-..   \ | /   ..-============.______\`.
 .'______________________________\|/______________________________`.
*/