2024 icpc 第二场网络赛题解

比赛链接：https://qoj.ac/contest/1799

A. Gambling on Choosing Regionals

题意

有 $n$ 个队伍，$k$ 个赛站，对于第 $i$ 个赛站，一个学校最多能派 $c_i$ 个队伍参加这个赛站。

第 $i$ 个队伍的能力值大小为 $w_i$，所属学校为 $s_i$。

一个队伍可以参加两个赛站，能力大小越大，队伍的排名越前，题目保证队伍的能力大小各不相同。

问在最坏的情况下，每个队伍的最小排名是多少？

数据范围

$1\le n,k\le 10^5,1\le c_k\le 10^9,1\le |s_i|\le 10$

思路

先来理解这个最坏情况是什么？
这个最坏情况指的是一个队伍参加比赛，会有尽可能多的队能力值比该队伍大， 从而使得这个队伍排名变大。

对于特定的队伍，能力值比这个队伍大的队伍的数量是固定的，而每个赛站同一个学校派出的最大队伍数是不一样的，所以影响队伍排名大小的是选择的赛站。

显然，选择 $c_i$ 前二小的赛站是最优的，因为赛站越小，能力值比当前队伍大的队伍能参加的越少。

因为一个队伍能参加两个赛站，所以有多少个比当前队伍能力值大的队伍参加了 $c_i$ 次小的赛站，这些队伍也能选择参加 $c_i$ 最小的赛站，使得当前队伍的排名最大化。

可是，也可能存在同校的问题，使得在 $c_i$ 最小的赛站，比当前队伍能力值大的队伍有部分无法参加，因此，参加 $c_i$ 最小的赛站获得的最小排名，就是当前队伍在最坏情况下能获得的最小排名。

可以把队伍按能力值大小从大到小排序，从前往后遍历队伍，同时记录当前遍历的队伍为止，所有的学校对应的队伍出现次数。

因为考虑的是 $c_i$ 最小的赛站，所以每个学校对应的队伍出现次数上界是 $min(c_i)(1\le i\le k)$，如果到达上界则该学校对应的队伍出现次数不再增加。

因为当前遍历的队伍必然排在前面的队伍之后，所以若遍历第 $i$ 个队伍，所有学校的队伍的出现次数为 $cnt$，那么第 $i$ 个队伍的可能最小排名即为 $cnt$。

复杂度

时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$

代码实现

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fs first
#define sc second

typedef pair<array<int, 2>, string> PAS;

const int N = 1e5 + 5;

int n, k;
int ans[N];
vector<PAS> arr;
unordered_map<string, int> cnt;

void solve()
{
    cin >> n >> k;
    int cm = 1e9;
    for (int i = 1; i <= k; i++) {
        int ci;
        cin >> ci;
        cm = min(cm, ci);
    }
    for (int i = 1; i <= n; i++) {
        int w;
        string s;
        cin >> w >> s;
        arr.push_back({ { w, i }, s });
    }
    sort(arr.begin(), arr.end(), greater<PAS>());

    int cur = 0;
    // 记录遍历到当前队伍，总的队伍出现次数（在cm的限制下）
    for (auto it : arr) {
        int id = it.fs[1];
        string s = it.sc;
        if (cnt[s] < cm) {
            cur++;
            cnt[s]++;
        }
        ans[id] = cur;
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << '\n';
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

F. Tourist

题意

初始分数为 $1500$，有 $n$ 次分数变动，第 $i$ 次分数变动为增加 $c_i$ 分。

问在第几次分数变动后，分数不低于 $4000$ 分？

如果不存在输出 $-1$。

数据范围

$1\le n\le 10^5,0\le |c_i|\le 10^9$

思路

按题意模拟即可。

复杂度

时间复杂度 $O(n)$，空间复杂度 $O(1)$

代码实现

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    int n;
    cin >> n;

    int cur = 1500;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        cur += x;
        if (cur >= 4000) {
            cout << i;
            return;
        }
    }
    cout << "-1";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

G. Game

题意

起初 $Alice$ 有 $x$ 个石子，$Bob$ 有 $y$ 个石子。
游戏会进行若干轮，$Alice$ 赢一轮的概率为 $p_0$，$Bob$ 赢一轮的概率为 $p_1$，两人平局的概率为 $1-p_0-p_1$。

如果两人平局，则什么都不发生，进入下一轮。
否则，如果赢家的石子数不小于输家的石子数，则赢家赢得整场游戏的胜利；如果赢家的石子数小于输家的石子数，那么输家的石子数会减少和当前赢家石子数相同的数量，然后进入下一轮。
问 $Alice$ 赢得整场游戏的胜利的概率是多少？
（答案要对 $998244353$ 取模）

数据范围

$1\le T\le 10^5,T为数据组数$
$1\le x,y\le 10^9$
$1\le a_0+a_1\le b<998244353$，表示 $p_0=\frac{a_0}{b},p_1=\frac{a_1}{b}$

思路

因为平局是不会影响当前状态的，所以不需要考虑平局的情况，此时要么赢要么输，赢的概率变为 $q_0=\frac{p_0}{p_0+p_1}=\frac{\frac{a_0}{b}}{\frac{a_0}{b}+\frac{a_1}{b}}=\frac{a_0}{a_0+a_1}$，同理输的概率变为 $q_1=\frac{p_1}{p_0+p_1}=\frac{a_1}{a_0+a_1}$。

如果当前 $x\ge y$，$Bob$ 需要赢 $\lfloor \frac{x}{y}\rfloor$ 局才能使得 $x<y$，那么 $Alice$ 获胜的情况要么 $Bob$ 赢 $x(0\le x<\lfloor \frac{x}{y}\rfloor )$ 轮后，$Alice$ 再赢一轮，对应的概率为 $q_0{\sum }_{i=0}^{\lfloor \frac{x}{y}\rfloor -1}{q}_1^i=q_0\ast (\frac{1-q_1^{\lfloor \frac{x}{y}\rfloor }}{1-q_1})$，要么是以 $q_0^{\lfloor \frac{x}{y}\rfloor }$ 的概率转换到 $x<y$ 的状态（$x$ 变成 $x\mathrm{mod}y$，$y$ 不变），然后 $Alice$ 最终获胜。

如果当前 $x<y$，只要 $Bob$ 赢一轮，$Bob$ 就获胜了，只有 $Alice$ 连续赢 $\lfloor \frac{y}{x}\rfloor$ 局，转换到 $x\ge y$ 的状态，才会存在 $Alice$ 获胜的情况，转换到 $x\ge y$ 的状态（ $x$ 不变，$y$ 变成 $y\mathrm{mod}x$）的概率为 $p_0^{\lfloor \frac{y}{x}\rfloor }$。

可以发现，在 $Alice$ 获胜概率的求解过程中，$x\ge y$ 和 $x<y$ 的状态是交替转换的，但是 $x,y$ 会一直减小，所以可以用一个变量 $ans$ 记录 $Alice$ 的获胜概率，直到到达 $x=0$ 或者 $y=0$ 的状态为止。

如果 $x=0$，说明此时 $Bob$ 获胜了。
如果 $y=0$，说明此时 $Alice$ 获胜了，如果到达当前状态的概率为 $cur$，则 $Alice$ 存在 $cur$ 的概率获胜，把 $cur$ 加到 $ans$ 中。

如果到达 $x\ge y$ 状态的概率为 $cur$，那么 $Alice$ 会存在 $cur\ast q_0\ast (\frac{1-q_1^{\lfloor \frac{x}{y}\rfloor }}{1-q_1})$ 的概率获胜，把该概率加到 $ans$之中，然后转移到下一个状态 $x<y$（$x$ 变成 $x\mathrm{mod}y$，$y$ 不变） ，到达的下一个状态概率为 $cur\ast q_0^{\lfloor \frac{x}{y}\rfloor }$。

如果到达 $x<y$ 状态的概率为 $cur$，则转移到下一个状态 $x\ge y$（ $x$ 不变，$y$ 变成 $y\mathrm{mod}x$），对应的到达概率为 $cur\ast p_0^{\lfloor \frac{y}{x}\rfloor }$。

可以发现，状态转换的方式是和辗转相除法一样的，这个计算过程的复杂度为 $O(\log max(x,y))$，因为需要用快速幂求逆元和次幂，所以总的复杂度为 $O({\log }^{2}max(x,y))$。

复杂度

时间复杂度 $O({\log }^{2}max(x,y))$，空间复杂度 $O(1)$

代码实现

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mod = 998244353;

int x, y, a0, a1, b, p0, p1, ans;

int qmi(int a, int b)
{
    int res = 1;
    a %= mod;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

int inv(int x)
{
    return qmi(x % mod, mod - 2);
}

void dfs(int cur, int x, int y)
{
    // cout << x << ' ' << y << '\n';
    if (!x)
        return;
    if (!y) {
        ans = (ans + cur) % mod;
        return;
    }
    if (x < y) {
        dfs(cur * qmi(p0, y / x) % mod, x, y % x);
    } else {
        int k = x / y;
        int mul = (1 - qmi(p1, k) + mod) % mod * inv(1 - p1 + mod) % mod * p0 % mod;
        // cout << mul << '\n';
        ans = (ans + cur * mul % mod) % mod;
        dfs(cur * qmi(p1, k) % mod, x % y, y);
    }
}

void solve()
{
    cin >> x >> y >> a0 >> a1 >> b;
    p0 = a0 * inv(a0 + a1) % mod;
    p1 = a1 * inv(a0 + a1) % mod;
    // cout << p0 << ' ' << p1 << '\n';
    ans = 0;
    dfs(1, x, y);
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    // cout << inv(2) << '\n';
}

J. Stacking of Goods

题意

有 $n$ 个货物，每个货物有三个属性 $w,v,c$。

可以将货物从左到右任意排列，排列之后，若第 $i$ 个货物左边所有货物的 $w$ 之和为 $W$，则该货物的价值为 $v_i-c_i\ast W$。

问所有货物价值的总和的最小值可能是多少？

数据范围

$1\le n,w_i\le 10^5,1\le v_i\le 10^{12},0\le c_i\le \frac{v_i}{\sum w_i}$

思路

如果已经安排好了 $m$ 个货物，可以发现交换第 $m-1$ 个货物和第 $m-2$ 个货物，只会影响到第 $m-1,m-2$ 个货物的价值。

若前 $m-3$ 个货物的 $w$ 之和为 $S$，价值总和为 $V$，那么未交换之前，前 $m$ 个货物的价值总和为 $V+(v_{m-2}-c_{m-2}\ast S)+(v_{m-1}-c_{m-1}\ast (S+w_{m-2}))$，交换之后前 $m$ 个货物的价值总和为 $V+(v_{m-1}-c_{m-1}\ast S)+(v_{m-2}-c_{m-2}\ast (S+w_{m-1}))$。

如果未交换前的价值总和较大，那么满足 $V+(v_{m-2}-c_{m-2}\ast S)+(v_{m-1}-c_{m-1}\ast (S+w_{m-2}))<V+(v_{m-1}-c_{m-1}\ast S)+(v_{m-2}-c_{m-2}\ast (S+w_{m-1}))$，化简之后可以得到 $c_{m-2}\ast w_{m-1}<c_{m-1}\ast w_{m-2}$（$\frac{c_{m-2}}{w_{m-2}}<\frac{c_{m-1}}{w_{m-1}}$）。

通过上式，可以发现把 $\frac{c}{w}$ 较小的尽可能放在前面可以使得价值之和最小化，所以把货物按 $\frac{c}{w}$ 从小到大排序，然后计算对应的价值总和即为答案。

复杂度

时间复杂度 $O(n\log n)$，主要是排序的复杂度，空间复杂度 $O(n)$

代码实现

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e5 + 5;

int n;

struct node {
    int w, v, c;
} a[N];

int cmp(node& p1, node& p2)
{
    return p1.c * p2.w < p2.c * p1.w;
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].w >> a[i].v >> a[i].c;
    }
    sort(a + 1, a + 1 + n, cmp);

    int ans = 0, W = 0;
    for (int i = 1; i <= n; i++) {
        ans += a[i].v - a[i].c * W;
        W += a[i].w;
    }
    cout << ans;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

L. 502 Bad Gateway

题意

起始时，等概率的在 $[1,T]$ 中选择一个整数 $t_0$，设置初始时间为 $t_0$ 秒。

在每秒末尾，时间会减少一秒，同时罚时加一，如果减少到 $0$ 秒则结束。

同时，在每秒末尾可以进行一次操作，等概率的在 $[1,T]$ 中选择一个整数 $t_1$，重置时间为 $t_1$。

问可能的最小罚时是多少？以最简分数的形式输出。

数据范围

$1\le n\le 10^6,1\le T_i\le 10^9$

思路

令 $f(i)$ 为初始时间为 $i$ 秒的最小罚时。

因为初始时间等概率的为 $[1,T]$ 中的一个整数，所以可能的最小罚时 $\frac{1}{T}{\sum }_{i=1}^{T}f(i)$。

因为在每秒末尾要么不操作，要么重置时间。

如果不操作，相当于罚时加一，然后初始时间变为 $i-1$，对应的最小罚时为 $f(i-1)+1$。

如果重置时间，初始时间会等概率的变成 $[1,T]$ 中的一个整点 $j$，那么对应的最小罚时为 $1+\frac{1}{T}{\sum }_{j=1}^{T}f(j)$。

可以得到 $f(i)$ 的递推公式，$f(i)=min(f(i-1),\frac{1}{T}{\sum }_{j=1}^{T}f(j))+1$。

显然，$f(i)$ 是随着 $i$ 递增而递增的，具有单调性，若 $f(x)\le \frac{1}{T}{\sum }_{j=1}^{T}f(j)$，那么 $f(x-1)$ 也满足 $f(x-1)\le \frac{1}{T}{\sum }_{j=1}^{T}f(j)$。

因此，会存在一个初始时间 $x$，满足 $f(x)\le \frac{1}{T}{\sum }_{j=1}^{T}f(j)$，$f(x+1)>\frac{1}{T}{\sum }_{j=1}^{T}f(j)$。

1，初始时间 $t_0\le x$，因为对应的最小罚时 $f(t_0)\le \frac{1}{T}{\sum }_{j=1}^{T}f(j)$，所以要使得罚时最小化，最优操作就是不重置时间，对应的最小罚时为 $t_0$。

2，初始时间 $t_0>x$，$f(t_0)>\frac{1}{T}{\sum }_{j=1}^{T}f(j)$，要使得罚时最小化，需要不断重置时间，直到重置到不超过 $x$ 的时间点为止。

若重置到不超过 $x$ 的时间点，会有 $\frac{1}{x}$ 的概率重置到 $[1,x]$ 的任意一个时间点，这部分的最小罚时为 $\frac{1}{x}(1+2+...+x)=\frac{1}{x}\frac{x(1+x)}{2}=\frac{1+x}{2}$。

令 $p=\frac{x}{t}$，表示重置到不超过 $x$ 的时间点的概率。

若第 $i$ 次重置才重置到 $[1,x]$ 内的任意一个时间点，说明前 $i-1$ 次都是重置到 $[x+1,n]$ 内，第 $i$ 次重置到 $[1,x]$ 内，对应的概率为 $p(1-p{)}^{i-1}$，相应的最小罚时相当于重置到 $[1,x]$ 的最小罚时 $\frac{1+x}{2}$ 加上重置了 $i$ 次的罚时 $i$，然后乘上对应的概率，即 $(\frac{1+x}{2}+i)\ast p(1-p{)}^{i-1}$。

因为这个重置次数是不确定的，可能 $1$ 次，也可能 $2$ 次，也可能 $3$ 次，每种重置次数都存在着对应的概率，因此，所有可能的重置次数对应的最小罚时之和为初始时间 $t_0>x$ 对应的最小罚时，可以表示为 ${\sum }_{i=1}^{+\infty }(\frac{1+x}{2}+i)\ast p(1-p{)}^{i-1}=\frac{1+x}{2}+p{\sum }_{i=1}^{+\infty }i(1-p{)}^{i-1}$。

回忆一下，等比级数可以表示为如下形式：
$$\sum _{i=1}^{+\infty }{x}^i=\underset{n\to +\infty }{\lim }\sum _{i=1}^n{x}^i=\underset{n\to +\infty }{\lim }\frac{x(1-x^n)}{1-x}=\underset{n\to +\infty }{\lim }\frac{1-x^{n+1}}{1-x}$$

如果 $0<x<1$，那么 ${\lim }_{n\to +\infty }{x}^{n+1}=0$，等比级数 ${\sum }_{i=1}^{+\infty }{x}^i=\frac{1}{1-x}$。

注意到，等比级数的导数可以表示为 ${\sum }_{i=1}^{+\infty }i\ast x^{i-1}=\frac{1}{(1-x{)}^2}$（对等比级数的式子两边求导），恰好和上面最小罚时中 ${\sum }_{i=1}^{+\infty }i(1-p{)}^{i-1}$ 是一样的。

综上，初始罚时 $t_0>x$，对应的最小罚时为 $\frac{1+x}{2}+p\ast \frac{1}{(1-(1-p){)}^2}=\frac{1+x}{2}+\frac{1}{p}$。

初始时间 $t_0$ 有 $p$ 的概率为 $[1,x]$ 的时间点，这段区间的最小罚时为 $p\ast \frac{1}{x}(1+2+...+x)=p\ast \frac{1+x}{2}$，有 $1-p$ 的概率为 $[x+1,T]$ 的时间点，这段时间的最小罚时为 $(1-p)\ast (\frac{1+x}{2}+\frac{1}{p})$，这两部分加起来为 $\frac{1+x}{2}+\frac{1}{p}-1=\frac{1+x}{2}+\frac{T}{x}-1$，这个便是答案的随 $x$ 变化的函数。

对 $\frac{1+x}{2}+\frac{T}{x}-1$ 进行求导，得到 $-\frac{T}{x^2}+\frac{1}{2}$，令 $-\frac{T}{x^2}+\frac{1}{2}=0$，得到 $x=\sqrt{2T}$，在正半轴该导函数是单调递增的，意味着若 $x<\sqrt{2T}$，因为导函数小于 $0$，$\frac{1+x}{2}+\frac{T}{x}-1$ 呈递减趋势，否则呈递增趋势，所以 $\frac{1+x}{2}+\frac{T}{x}-1$ 在 $\sqrt{2T}$ 处取得极小值。（因为最后取得是整点，所以答案的极值点是在 $\sqrt{2T}$ 上下取整中的一个点）

因为代码实现的时候需要以分数形式输出，分数运算中涉及最小公倍数和最大公因子，需要用到辗转相除法，复杂度是 $O(\log T)$ 的。

复杂度

时间复杂度为 $O(\log T)$ ，空间复杂度为 $O(1)$

代码实现

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct val {
    int x, y;
    val(int _x, int _y)
    {
        int _g = __gcd(_x, _y);
        x = _x / _g, y = _y / _g;
    }
    val operator+(const val& it) const&
    {
        int ny = y / __gcd(y, it.y) * it.y;
        int nx = ny / y * x + ny / it.y * it.x;
        return val(nx, ny);
    }
    bool operator<(const val& it) const&
    {
        return x * it.y < it.x * y;
    }
};

void solve()
{
    int n;
    cin >> n;
    val ans(2e9, 1);
    int v = sqrt(2 * n);
    // v 为下取整的极值点，v+1 为上取整
    for (int i = 0; i <= 1; i++) {
        if (v + i > 0) {
            // 	(x+1)/2 + n/x - 1
            int x = v + i;
            val t = val(x + 1, 2) + val(n, x) + val(-1, 1);
            if (t < ans)
                ans = t;
        }
    }
    cout << ans.x << ' ' << ans.y << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}