26牛客暑假多校8

点击查看题面

I题 Bridge VI

题目大意

有 $2 n$ 名参赛者进行决赛，编号为 $1$ 到 $2 n$ 。参赛者 $i$ 初始得分为 $a_{i}$ 。比赛分为 $n$ 场，第 $i$ 场比赛由参赛者 $2 i - 1$ 与参赛者 $2 i$ 对决，每场比赛有 $m$ 分可以以任意非负实数形式分配给两人（即两人的得分增加量 $x, y \geq 0$ 满足 $x + y = m$ ）。

参赛者 $1$ （大豆）希望了解：

最少有多少名参赛者的最终得分严格大于大豆的最终得分。
最多有多少名参赛者的最终得分严格大于大豆的最终得分。

数据范围：

$1 \leq t \leq 10^{4}$
$1 \leq n \leq 2 \cdot 10^{5}$ ，且 $\sum n \leq 2 \cdot 10^{5}$
$1 \leq m \leq 10^{9}$
$1 \leq a_{i} \leq 10^{9}$

思路

假设大豆（参赛者 $1$ ）在第 $1$ 场比赛中获得 $x$ 分（ $0 \leq x \leq m$ ），则其对手（参赛者 $2$ ）获得 $m - x$ 分。

1. 计算最少严格大于大豆的人数 $x_{a n s}$ （最佳排名）

要让超过大豆的人数最少，应尽可能提高大豆的分数，故取 $x = m$ 。

大豆最终得分 $q = a_{1} + m$ 。
对手（参赛者 $2$ ）最终得分 $a_{2}$ 。若 $a_{2} > q$ ，则贡献 $1$ 人，否则贡献 $0$ 人。
对于其余 $n - 1$ 场比赛（假设两选手初始分分别为 $u, v$ ），每场增加的分数和为 $m$ ：
贡献 $2$ 人：若 $u > q$ 且 $v > q$ ，无论怎么分配 $m$ 分，两人最终得分均严格大于 $q$ 。
贡献 $0$ 人：若 $u \leq q$ 且 $v \leq q$ ，且满足分配后两人得分均 $\leq q$ ，即存在 $x_{i}, y_{i} \geq 0$ 使 $u + x_{i} \leq q, v + y_{i} \leq q, x_{i} + y_{i} = m$ 。这要求 $(q - u) + (q - v) \geq m ⟺ u + v + m \leq 2 q$ 。
贡献 $1$ 人：其余情况，由于至少有一个人初始分 $\leq q$ ，可将全部 $m$ 分分配给另一人，保证初始分 $\leq q$ 者最终得分仍 $\leq q$ ，故可控制增加人数为 $1$ 。

2. 计算最多严格大于大豆的人数 $y_{a n s}$ （最差排名）

要让超过大豆的人数最多，应尽可能降低大豆的分数，故取 $x = 0$ 。

大豆最终得分 $p = a_{1}$ 。
对手（参赛者 $2$ ）最终得分 $a_{2} + m$ 。若 $a_{2} + m > p$ ，则贡献 $1$ 人，否则贡献 $0$ 人。
对于其余 $n - 1$ 场比赛（假设两选手初始分分别为 $u, v$ ）：
贡献 $2$ 人：若能使两人最终得分均严格大于 $p$ ，即存在 $x_{i}, y_{i} \geq 0$ 使 $u + x_{i} > p$ 且 $v + y_{i} > p$ 。因为得分可为实数，这等价于所需额外分数的严格下界和小于 $m$ ，即 $max (0, p - u) + max (0, p - v) < m$ 。
贡献 $1$ 人：若无法做到两个人均超过 $p$ ，但将所有 $m$ 分给其中一人可使其超过 $p$ （即 $u + m > p$ 或 $v + m > p$ ）。
贡献 $0$ 人：即使把 $m$ 分全给某一人也无法超过 $p$ 。

复杂度分析

时间复杂度： $O (n)$ 。对于每组测试用例，只需遍历 $n$ 场比赛进行常数次算术与条件判断，总时间复杂度与 $\sum n$ 成线性关系。 空间复杂度： $O (1)$ 。算法仅维护常数个变量存储得分与计数，无需额外空间。

参考代码

cpp

#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

void solve() {
    int n;
    ll m;
    cin >> n >> m;
    
    ll a0, a1;
    cin >> a0 >> a1;
    
    // q: 大豆能拿到的最大最终得分（用于计算最少超越人数）
    // p: 大豆能拿到的最小最终得分（用于计算最多超越人数）
    ll q = a0 + m, p = a0;
    
    ll x_ans = (a1 > q ? 1 : 0);
    ll y_ans = (a1 + m > p ? 1 : 0);
    
    for (int i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        
        // 1. 评估极小化超越人数贡献
        if (u > q && v > q) {
            x_ans += 2;
        } else if (u > q || v > q || u + v + m > 2 * q) {
            x_ans += 1;
        } 
        
        // 2. 评估极大化超越人数贡献
        ll req = max(0LL, p - u) + max(0LL, p - v);
        if (m > req) {
            y_ans += 2;
        } else if (u + m > p || v + m > p) {
            y_ans += 1;
        } 
    }
    
    cout << x_ans << ' ' << y_ans << "\n";
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t = 1;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

G题 Multiplication

题目大意

在十进制表示下，给定三个正整数 $a, b, c$ 。要求构造两对正整数 $(x_{1}, y_{1})$ 与 $(x_{2}, y_{2})$ ，满足以下三个条件：

$x_{1}$ 与 $x_{2}$ 的长度均至少为 $a$ ，且前 $a$ 位完全相同。
$y_{1}$ 与 $y_{2}$ 的长度均至少为 $b$ ，且前 $b$ 位完全相同。
乘积 $P_{1} = x_{1} \cdot y_{1}$ 与 $P_{2} = x_{2} \cdot y_{2}$ 的长度均至少为 $c$ ，但两者的前 $c$ 位不相同。

数据范围：

$1 \leq a, b \leq 10^{5}$
$1 \leq c < a + b - 1$

思路

为了使 $P_{1}$ 与 $P_{2}$ 的前 $c$ 位不相同（ $c \geq 1$ ），最直接的做法是让 $P_{1}$ 的首位数字为 $9$ ，而 $P_{2}$ 的首位数字为 $1$ 。

根据 $a$ 与 $b$ 的大小关系分类构造：

1. 当 $a \geq b$ 时

令 $x_{1} = \underset{a}{\underset{⏟}{99 \dots 9}} = 10^{a} - 1$ ， $y_{1} = 1 \underset{b - 1}{\underset{⏟}{00 \dots 0}} = 10^{b - 1}$ （长度为 $b$ ）。
令 $x_{2} = \underset{a}{\underset{⏟}{99 \dots 9}} = 10^{a} - 1$ ， $y_{2} = 1 \underset{b - 1}{\underset{⏟}{00 \dots 0}} 9 = 10^{b} + 9$ （长度为 $b + 1$ ）。

正确性验证：

$x_{1}$ 与 $x_{2}$ 完全相同，前 $a$ 位显然相同。
$y_{1}$ 长度为 $b$ （为 $100 \dots 0$ ）， $y_{2}$ 长度为 $b + 1$ （为 $100 \dots 09$ ），前 $b$ 位均为 $100 \dots 0$ ，完全相同。
计算乘积：

P_{1} = x_{1} \cdot y_{1} = (10^{a} - 1) \cdot 10^{b - 1} = \underset{a}{\underset{⏟}{99 \dots 9}} \underset{b - 1}{\underset{⏟}{00 \dots 0}}

其首位数字为 $9$ 。

P_{2} = x_{2} \cdot y_{2} = (10^{a} - 1) \cdot (10^{b} + 9) = 10^{a + b} + 9 \cdot 10^{a} - 10^{b} - 9

由于 $a \geq b \geq 1$ ，最高项为 $10^{a + b}$ ，其系数为 $1$ ，故 $P_{2}$ 的首位数字为 $1$ 。

$P_{1}$ 首位为 $9$ ， $P_{2}$ 首位为 $1$ ，从第 $1$ 位起即不相同，故对任意 $1 \leq c < a + b - 1$ ，前 $c$ 位均不相同。

2. 当 $a < b$ 时

对称地将低位扰动施加在 $x$ 上：

令 $x_{1} = 1 \underset{a - 1}{\underset{⏟}{00 \dots 0}}$ ， $y_{1} = \underset{b}{\underset{⏟}{99 \dots 9}}$ 。
令 $x_{2} = 1 \underset{a - 1}{\underset{⏟}{00 \dots 0}} 9$ ， $y_{2} = \underset{b}{\underset{⏟}{99 \dots 9}}$ 。同理可得 $P_{1}$ 首位为 $9$ ， $P_{2}$ 首位为 $1$ ，满足要求。

复杂度分析

时间复杂度： $O (a + b)$ 。只需利用字符串构造并输出四个大整数，输出字符总量为 $O (a + b)$ 。
空间复杂度： $O (a + b)$ 。构造过程使用常数个临时字符串，占用空间与输入参数成线性关系。

参考代码

cpp

#include <iostream>
#include <string>

using namespace std;

void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    
    // 根据 a 和 b 的大小关系分情况构造，确保进位效果成立
    if (a >= b) {
        // x1 = a个9, y1 = '1' + (b-1)个0
        // x2 = a个9, y2 = '1' + (b-1)个0 + '9'
        cout << string(a, '9') << " " << '1' + string(b - 1, '0') << " ";
        cout << string(a, '9') << " " << '1' + string(b - 1, '0') + '9' << "\n";
    } else {
        // x1 = '1' + (a-1)个0, y1 = b个9
        // x2 = '1' + (a-1)个0 + '9', y2 = b个9
        cout << '1' + string(a - 1, '0') << " " << string(b, '9') << " ";
        cout << '1' + string(a - 1, '0') + '9' << " " << string(b, '9') << "\n";
    }
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t = 1; 
    while (t--) {
        solve();
    }
    return 0;
}

B题 Deep Finesse

题目大意

汐与风子在包含 $1$ 到 $10^{100}$ 所有整数的数字宇宙中进行 $n$ 轮博弈。汐选择 $n$ 个互不相同的数字作为手牌，其余所有数字归风子所有。

每轮由风子先手打出一个数字，汐必须用一个尚未打出的手牌回应：

若汐的回应数字 $\leq$ 风子的数字，该轮安全度过。
若汐的回应数字 $>$ 风子的数字，风子立即获胜。

汐已知手牌中必须包含给定的 $m$ 个指定数字 $a_{1}, a_{2}, \dots, a_{m}$ 。请计算在所有符合要求的大小为 $n$ 的手牌中，有多少种手牌能保证汐存在必胜策略。结果对 $998244353$ 取模。

数据范围：

测试用例数 $t \leq 1000$ 。
$1 \leq m \leq n \leq 5000$ ，且 $\sum n \leq 5000$ 。
$1 \leq a_{i} \leq 10^{9}$ ，且 $a$ 中无重复元素。

思路

充要条件推导：

风子为了获胜，最优策略是按从小到大的顺序打出自己手上的牌。
设汐在 ${1, 2, \dots, i}$ 中的手牌数量为 $c_{i}$ 。风子在该区间内的牌数为 $i - c_{i}$ 。
若存在某个 $i$ 使得 $i - c_{i} > c_{i}$ （即 $c_{i} < ⌈ i / 2 ⌉$ ），风子只需依次打出这 $i - c_{i}$ 张牌，汐手中能回应的牌至多只有 $c_{i}$ 张，必定会被逼出 $> i$ 的牌而输掉比赛。
因此，必胜的充要条件为：对任意 $i \in {1, 2, \dots, 2 n - 1}$ ，均有 $c_{i} \geq ⌈ \frac{i}{2} ⌉$ 。
当 $i = 2 n - 1$ 时， $c_{2 n - 1} \geq n$ ，意味着汐的所有手牌必须全分布于 $[1, 2 n - 1]$ 中。若给定的指定数字中存在 $a_{k} \geq 2 n$ ，则必胜方案数为 $0$ 。

状态定义与转移方程：

设 $d p [j]$ 表示在考虑前 $i$ 个数字时，汐已选择 $j$ 个数字作为手牌的方案数。
遍历 $i$ 从 $1$ 到 $2 n - 1$ ：
当前选取数量的合法区间为 $j \in [m n, m x]$ ，其中 $m n = ⌊ (i + 1) / 2 ⌋$ ， $m x = min (i, n)$ 。
若 $i$ 为必选数字（在给定的集合中），必须选择该数字，转移方程为：

d p [j] = d p [j - 1]

若 $i$ 为非必选数字，可选择或不选择，转移方程为：

d p [j] = (d p [j] + d p [j - 1]) (\mod 998244353)

对于 $j < m n$ 的状态，强制置 $d p [j] = 0$ 。

目标结果：

最终 $d p [n]$ 即为满足前缀限制且包含所有指定数字的有效手牌方案总数。

复杂度分析

时间复杂度：对于每组测试用例，遍历长度为 $2 n - 1$ ，DP 状态更新次数为 $O (n)$ ，单次用例复杂度为 $O (n^{2})$ 。总时间复杂度为 $O (\sum n^{2}) \leq O ((\sum n)^{2})$ ，完全符合 2 秒的时限要求。

空间复杂度：由于采用了倒序更新的一维滚动 DP 数组，空间复杂度为 $O (n)$ 。

参考代码

cpp

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

const ll mod = 998244353;

void solve() {
    int n, m;
    cin >> n >> m;
    
    bool valid = true;
    vector<bool> forced((n << 1) + 1, false);
    
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x; 
        if (x >= (n << 1)) {
            valid = false;
        } else {
            forced[x] = true;
        }
    }
    
    if (!valid) {
        cout << "0\n";
        return;
    }
     
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
     
    for (int i = 1; i < (n << 1); i++) {
        int mn = (i + 1) >> 1; 
        int mx = min(i, n);     
         
        for (int j = mx; j >= mn; j--) {
            if (forced[i]) {
                dp[j] = dp[j - 1];  
            } else {
                dp[j] = (dp[j] + dp[j - 1]) % mod; 
            }
        }
         
        for (int j = 0; j < mn; j++) {
            dp[j] = 0;
        }
    }
    
    cout << dp[n] << "\n";
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

H题 It’s Magic, Not a Trick!

题目大意

梦野秘密子面前有 $n$ 张符咒，第 $i$ 张符咒初始拥有 $a_{i}$ 单位能量。她可以执行任意多次施法过程，每次施法必须按顺序包含以下两步：

灌注：选择任意一张符咒，使其能量 $+ 1$ 。
释放：选择任意一张能量 $\geq x$ 的符咒，使其能量 $- x$ 。

约束条件：若灌注后没有任何符咒的能量达到或超过 $x$ ，则施法失败且无法执行。所有符咒的能量必须始终非负。

求在保证每次施法均成功的前提下，所有符咒最终剩余能量之和的最小值，答案对 $998244353$ 取模。

数据范围：

$t \leq 10^{4}$ （测试用例数）
$\sum n \leq 2 \times 10^{5}$
$1 \leq x \leq 10^{9}$
$1 \leq a_{i} \leq 10^{18}$

思路

等价转化与净收益分析：单次成功的施法需要注入 $1$ 单位能量，并扣除 $x$ 单位能量，因此总能量净减少 $x - 1$ 。若 $x = 1$ ，则每次操作总能量不发生改变，答案即为 $\sum a_{i} (\mod 998244353)$ 。当 $x > 1$ 时，目标是尽可能多地执行合法施法。
单单元基础释放次数计算：对于第 $i$ 张符咒，在其自身 $a_{i}$ 单位能量的基础上，考虑到触发释放前需要先执行一次 $+ 1$ 的灌注，该符咒独自能够支持的最大释放次数为：

l_{i} = ⌊ \frac{a_{i} + 1}{x} ⌋

在完成 $l_{i}$ 次释放后，该符咒自身保留的必要能量为：

c_{i}^{r e m} = max (0, a_{i} - l_{i} \cdot x)

自由能量池 ( $p o o l$ ) 的构建：所有符咒在完成 $s l = \sum l_{i}$ 次基础释放后，系统剩余的总能量为 $a n s = \sum a_{i} - (x - 1) \cdot s l$ 。其中，必须留存在各个符咒内部、无法自由挪用的静态能量和为 $s c = \sum c_{i}^{r e m}$ 。因此，能够被动态调配用于“补齐缺口”的自由能量池大小为：

p o o l = a n s - s c

贪心补齐策略：若要让第 $i$ 张符咒额外再触发一次释放，除了利用下一次施法自带的 $1$ 点灌注外，还需要从自由能量池中补充的能量缺口为：

c_{i} = x - c_{i}^{r e m} - 1

为了用有限的 $p o o l$ 换取尽可能多的额外释放次数，我们将所有 $c_{i}$ 从小到大排序。按顺序遍历 $c_{i}$ ：若 $p o o l \geq c_{i}$ ，则消耗 $c_{i}$ 单位能量池储备，使得总释放次数增加 $1$ （即 $a n s \leftarrow a n s - (x - 1)$ ），并更新 $p o o l \leftarrow p o o l - c_{i}$ 。 5. 剩余能量池的二次利用：遍历结束后，若 $p o o l$ 无法完整满足任何单个符咒的独立缺口，但只要 $x > 1$ ，剩余的 $p o o l$ 仍然可以通过多张符咒间的协同灌注继续消耗。每消耗 $(x - 1)$ 单位自由能量，即可额外完成一次施法：

a n s \leftarrow a n s - ⌊ \frac{p o o l}{x - 1} ⌋ \cdot (x - 1)

大数处理与取模：由于 $a_{i} \leq 10^{18}$ ，累加与乘法过程中需使用 __int128 避免溢出，最终将结果对 $998244353$ 取模输出。

复杂度分析

时间复杂度：数据输入与基础状态计算为 $O (n)$ ，对补齐成本数组 $c$ 进行排序耗时 $O (n \log n)$ 。多组测试用例下，总时间复杂度为 $O (\sum n \log n)$ ，完全符合 $2 seconds$ 的时间限制。
空间复杂度：需要结构化数组存储 $a_{i}, l_{i}, c_{i}$ ，空间复杂度为 $O (n)$ ，符合 $1024 MB$ 的内存限制。

参考代码

cpp

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

void fc() {
    ll n, x;
    std::cin >> n >> x;
    std::vector<ll> l(n), c(n), a(n);
    __int128 sa = 0, sl = 0;
    ll sc = 0;

    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        sa += a[i];
        // l[i]: 结合本次施法自带的 1 点灌注，当前符咒独立可支持的最大释放次数
        l[i] = (a[i] + 1) / x;
        // c[i]: 完成 l[i] 次释放后剩余的保留能量
        c[i] = std::max(0LL, a[i] - l[i] * x);
        sl += l[i];
        sc += c[i];
        // 重新定义 c[i] 为额外再触发一次释放所需的补齐能量缺口
        c[i] = x - c[i] - 1;
    }
    
    // ans: 完成所有基础释放后的系统剩余总能量
    // pool: 扣除不可自由调配的保留能量后，可用于补齐缺口的自由能量池
    __int128 ans = sa - (x - 1) * sl, pool = ans - sc;
    
    // 贪心策略：优先补齐缺口最小的符咒，以获得额外的释放次数
    std::sort(c.begin(), c.end());
    for (int i = 0; i < c.size(); i++) {
        if (pool < c[i]) break;
        pool -= c[i];
        ans -= x - 1;
    }
    
    // 剩余自由能量池若大于等于 (x - 1)，可继续进行组合释放
    if (x > 1) {
        ans -= pool / (x - 1) * (x - 1);
    }
    
    ll s = ans % 998244353;
    std::cout << s << "\n";
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t = 1;
    std::cin >> t;
    while (t--) fc();
    return 0;
}

26牛客暑假多校8 ​

I题 Bridge VI ​

题目大意 ​

思路 ​

1. 计算最少严格大于大豆的人数 xans（最佳排名） ​

2. 计算最多严格大于大豆的人数 yans（最差排名） ​

复杂度分析 ​

参考代码 ​

G题 Multiplication ​

题目大意 ​

思路 ​

1. 当 a≥b 时 ​

2. 当 a<b 时 ​

复杂度分析 ​

参考代码 ​

B题 Deep Finesse ​

题目大意 ​

思路 ​

复杂度分析 ​

参考代码 ​

H题 It’s Magic, Not a Trick! ​

题目大意 ​

思路 ​

复杂度分析 ​

参考代码 ​

26牛客暑假多校8

I题 Bridge VI

题目大意

思路

1. 计算最少严格大于大豆的人数 $x_{a n s}$ （最佳排名）

2. 计算最多严格大于大豆的人数 $y_{a n s}$ （最差排名）

复杂度分析

参考代码

G题 Multiplication

题目大意

思路

1. 当 $a \geq b$ 时

2. 当 $a < b$ 时

复杂度分析

参考代码

B题 Deep Finesse

题目大意

思路

复杂度分析

参考代码

H题 It’s Magic, Not a Trick!

题目大意

思路

复杂度分析

参考代码