专栏文章

题解：CF626D Jerry's Protest

aa_small_penguin
CF626D题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mipgxags
此快照首次捕获于
2025/12/03 11:49
3 个月前
此快照最后确认于
2025/12/03 11:49
3 个月前
查看原文
什么是 DP？布吉岛……
于是我用前缀和淼过去了。
首先，设 Andrew 取得数是 a1,a2,a3a_1,a_2,a_3，Jerry 取得数是 b1,b2,b3b_1,b_2,b_3。
即题目问 a1>b1,a2>b2a_1 > b_1, a_2 > b_2，但 a1+a2+a3<b1+b2+b3a_1+a_2+a_3<b_1+b_2+b_3 的概率是多少。
对于最后要求的式子 a1+a2+a3<b1+b2+b3a_1+a_2+a_3<b_1+b_2+b_3 进行变形：
a1+a2+a3<b1+b2+b3a_1+a_2+a_3 < b_1+b_2+b_3 等价于 (a1−b1)+(a2−b2)+(a3−b3)<0(a_1-b_1)+(a_2-b_2)+(a_3-b_3) < 0。那么进行换元：a1−b1=c1,a2−b2=c2,a3−b3=c3a_1-b_1 = c_1,a_2-b_2=c_2,a_3-b_3=c_3。故可以继续转化为 c1+c2+c3<0c_1 + c_2 + c_3 < 0。
考虑暴力，暴力就是枚举 c1c_1、c2c_2、c3c_3 的值，再判断符不符合题目要求，再进行计算概率。
如何优化？
对式子继续转化。得 −(c1+c2)>c3-(c_1 + c_2) > c_3。
而 c1,c2c_1,c_2 的范围是固定的，1≤c1,c2≤49991\le c_1,c_2 \le 4999。就可以枚举 c1,c2c_1,c_2。且此时 c3c_3 的范围也是固定的，−4999≤c3<−(c1+c2)-4999 \le c_3 < -(c_1 + c_2)。因为此时 c3c_3 的上界和下界都已确定，所以就可以进行前缀和优化。
时间复杂度：O((n+w)2+n)O((n + w)^2 + n)，其中 ww 代表值域范围。
code：
CPP
#include <bits/stdc++.h>
using namespace std;

int n;
int a[2009];

long double f[10009];
long double d[10009];

long double ans;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(i == j) continue;
            f[a[i] - a[j] + 5000]++; // 进行下标偏移
        }
    }
    for(int i = 1; i <= 10000; i++) {
        f[i] /= (long double)((n - 1) * n / 2.0);
        d[i] = d[i - 1] + f[i];
    }
    for(int i = 5001; i <= 9999; i++) {
        for(int j = 5001; j <= 9999; j++) {
            if(5000 - (i + j - 10000) - 1 < 0) continue;
            ans += f[i] * f[j] * d[5000 - (i + j - 10000) - 1];
        }
    }
    printf("%.5291Lf", ans);


    return 0;

} // I am a deep well ice

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...