P13800 [SWERC 2023] Throwing dice 题解

题目大意

Alice 和 Bob 掷出自己的骰子，将骰子显示的点数相加，然后比较总和。总和较大的玩家获胜；如果双方总和相等，则为平局。

Alice 有 个公骰子，第 个骰子有 个面。对于每一个骰子，得到每一个面的概率是相等的。Alice 的得分是她所有 个骰子显示的数字之和。类似地，Bob 有 个公平骰子，第 个骰子有 个面。

Alice 得分严格大于 Bob 的概率为 ，而 Bob 得分严格大于 Alice 的概率为 。如果 ，输出 ；如果 ，输出 ；如果 ，输出 。

思路

期望 - OI-Wiki

每个骰子的分布是对称的（均匀分布），因此多个骰子总和的分布成正态分布。设 为 Alice 的总分数， 为 Bob 的总分数，则 和 都是对称随机变量。

令 。由于正态分布：

• 如果 ，则 的分布中心在 的分布中心右侧，因此 。
• 如果 ，则 。
• 如果 ，则 。

因此，直接比较总期望值 和 即可判断谁获胜概率更大。（题目标签也是期望）

纯暴力写法

通过暴力枚举所有的期望，相加，公式：

#include <cstdio>
#define MAXN 1000001
int n, m, a[MAXN], b[MAXN];
double Alice, Bob;
int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &b[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= a[i]; j++)
        {
            Alice += j / a[i] * 1.0;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= b[i]; j++)
        {
            Bob += j / b[i] * 1.0;
        }
    }
    if (Alice == Bob)
    {
        printf("TIED");
    }
    else if (Alice > Bob)
    {
        printf("ALICE");
    }
    else
    {
        printf("BOB");
    }
    return 0;
}

时间复杂度：

会超时，提交记录

空间复杂度：

第一次优化

上文公式可以优化，不难发现第二层循环可以将 提取出来，即：

将分子替换成求和公式，即

不难发现，每一次的加法操作只和当前的 有关，可以将 数组简化为单个变量

代码如下：

#include <cstdio>
int n, m, a, b;
double Alice, Bob;
int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d", &a);
        Alice += (a + 1.0) / 2.0; // 注意此处的精度问题
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &b);
        Bob += (b + 1.0) / 2.0;
    }
    if (Alice == Bob)
    {
        printf("TIED");
    }
    else if (Alice > Bob)
    {
        printf("ALICE");
    }
    else
    {
        printf("BOB");
    }
    return 0;
}

时间复杂度：

空间复杂度：