2024 ICPC EC 第二场网络预选赛

这一场其实是队友带飞的，但是还是来补一下题。

A. Gambling on Choosing Regionals

最核心的点就是，对于某只队伍 $t_i$ 最坏情况下其他学校都派最强的队伍来和这支队伍竞争，那么可想而知，如果学校越多，那么很有可能其他学校的强队全都来了，那么自己的机会就越来越小了，所以核心的点就是一定选择最小的赛站。

因为 $t_i$ 总是有优先权，因此对于 $t_i$ 来说，在他之上的队伍由两部分组成（假设最小的赛站，每个学校可以出 $c$ 支队伍）

• 其他学校的所有强队，数量 $\le c$
• 本学校的强队，数量 $\le c-1$。因为包含 $t_i$

因此，我们直接对每只队伍的实力排序，先每个学校取前 $c$ 个，然后如果某个队伍不在其学校的前 $c$ 名，那么踢掉最后一名，把这支队伍换上来。总时间复杂度 $O(n\log n)$.

G. Game

首先我们要看出来平局其实没有用（因为不会产生任何影响）。我们直接令 $p_1=\frac{a_0}{a_0+a_1},p_2=\frac{a_1}{a_0+a_1}$.

然后分别考虑两人的筹码数和获胜条件，设 Alice 有 $a$ 个筹码，Bob 有 $b$ 个

1. 如果 $a>=b$，令 $a=kb+r,r\in[0,b)$

   此时，Alice 只要在这 $k$ 次里赢一次，游戏就结束了。

   这里的分布是“有 $p_1$ 概率获胜， continue until first win”，其获胜概率为 $\sum_{i=0}^k p_1 p_2^i=\frac{1-p_2^k}{1-p_2}\times p_1$

   然而，如果全输了，那么 $r\lt b$ 会进入 2) 分支。综合一下，即为 $win(a,b)=\frac{1-p_2^k}{1-p_2}p_1+p_2^k\times win(r, b)$

2. 如果 $a<b$，令 $b=ka+r,r\in[0, a)$

   此时局面刚好反过来，Alice 要想获胜，必须保证这 $k$ 次不能输（否则游戏结束）

   当这 $k$ 全赢了之后，局面回到 1)。因此 $win(a,b)=p_1^k\times win(a, r)$

而回顾 $win(x,y)$ 的参数变化，这不就是辗转相除法吗！因此整体时间复杂度为 $O(\log n)$，考虑到逆元、快速幂的计算（$p_1,p_2,k$ 与 $n$ 差不多量级），其实差不多是 $O(\log^2n)$

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

#include <iostream>

constexpr int M = 998244353;

inline int smul(int a, int b) { return (1ll * a * b < M ? a * b : 1ll * a * b % M); }
inline int sadd(int a, int b) { return (a + b >= M ? a + b - M : a + b); }

int fpow(int base, int power = M - 2) {
    int res = 1;
    for (; power; power >>= 1) {
        if (power & 1) res = smul(res, base);
        base = smul(base, base);
    }
    return res;
}

int answer(int a, int b, int win, int lose) {
    if (a == 0 || b == 0) return a != 0;
    if (a >= b) {
        int k = a / b, r = a % b;
        int c = fpow(lose, k);

        int numerator   = sadd(1, M - fpow(lose, k));                    // 1 - lose^k (mod M)
        int denominator = sadd(1, M - lose);                             // 1 - lose (mod M)
        int tmp         = smul(win, smul(numerator, fpow(denominator))); // Using modular inverse

        return sadd(smul(c, answer(r, b, win, lose)), tmp);
    } else {
        int k = b / a, r = b % a;
        int c = fpow(win, k);
        return smul(c, answer(a, r, win, lose));
    }
}

void run() {
    int a, b;
    int p1, p2, P;
    std::cin >> a >> b >> p1 >> p2 >> P;
    P  = p1 + p2;
    p1 = smul(p1, fpow(P)), p2 = smul(p2, fpow(P));

    std::cout << answer(a, b, p1, p2) << '\n';
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int T;
    std::cin >> T;
    while (T--) run();
}

L. 502 Bad Gateway

当当前时刻为 $1,2,3,\dots$ 的时候，按按钮重置时间反而得不偿失；相反，如果当前时刻比较大，那么重置时间更有可能缩短用时。

于是基于这一个观察，我们可以猜测：存在一个阈值 $c$，当时刻 $\lt c$ 我们就慢慢等；反之我们就一直按按钮，直到 $\lt c$ 为止。

根据我们的猜测，每摁一次按钮，重置到 $\lt c$ 的概率为 $p=\frac{c}{t}$. “不断按成功概率为 $p$ 的按钮，直到第一次成功停止”，诶，这不就是几何分布吗？