Codeforces Round 1122 (Div. 3)

点击查看题面

A. Good Contest

题目大意

在一场共有 $n$ 位选手的算法竞赛中包含 $3$ 道题目。选手若未完全解出所有 $3$ 道题目，则被称为 weak 选手。

记分榜数据丢失，仅保留了每道题目的通过人数统计数组 $a=[a_1,a_2,a_3]$，其中 $a_i$ 表示解出第 $i$ 道题目的选手数量。在所有满足该统计数据的有效记分榜中，求 weak 选手的最小可能数量。

数据范围：

• 测试用例组数 $t$ 满足 $1\le t\le 3000$。
• 参赛选手总人数 $n$ 满足 $1\le n\le 9$。
• 每道题解出人数 $a_i$ 满足 $0\le a_i\le n$（其中 $i\in \{1,2,3\}$）。

---

思路

本题的核心目标是在给定各题解出总人数的约束下，最小化未解出所有题目的选手人数。

1. 目标转化： 设解出全部 $3$ 道题目的选手数量为 $S$。根据题意，weak 选手即为未完全解出所有题目的选手，其数量为：

$$W=n-S$$

因此，最小化 weak 选手数量 $W$，等价于最大化完全解出所有题目的选手数量 $S$。

2. 理论上界推导： 任何解出全部 $3$ 道题目的选手，必然对每道题目的通过人数均贡献了 $1$。因此，解出全部题目的选手总数 $S$ 受限于通过人数最少的那道题，即：

$$S\le min(a_1,a_2,a_3)$$

3. 构造性证明（上界可达性）： 设 $k=min(a_1,a_2,a_3)$。我们可采取如下贪心分配方案：

• 选取编号为 $1,2,\dots ,k$ 的 $k$ 位选手，令他们均解出全部三道题目。此时每道题目均被消耗了 $k$ 个解出名额。
• 对于剩余的名额，第 $i$ 道题还剩余 $a_i-k$ 个名额。由于 $k=min(a_1,a_2,a_3)$，必存在至少一个维度使得剩余名额为 $0$。
• 将剩余的名额任意分配给编号在 $k+1$ 到 $n$ 的选手（每名选手在同一题上至多分配一次）。由于至少有一道题的剩余名额为 $0$，后续选手不可能同时获得全部三题的解出判定。

因此，该构造方案严格满足题目给定的统计值 $a_i$，且使得解出所有题目的选手数精确达到理论最大值 $S_{max}=min(a_1,a_2,a_3)$。

4. 最终结果： 最小化 weak 选手数量为：

$$W_{min}=n-min(a_1,a_2,a_3)$$

---

复杂度分析

• 时间复杂度：对于每组测试用例，仅需对三个数取最小值并执行一次减法操作，单组用例时间复杂度为 $\mathcal{O}(1)$。处理全部 $t$ 组测试用例的总时间复杂度为 $\mathcal{O}(t)$。
• 空间复杂度：算法仅需常数级别的变量存储输入与计算结果，空间复杂度为 $\mathcal{O}(1)$。

---

参考代码

参考代码

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

void fc() {
    int n, a, b, c;
    std::cin >> n >> a >> b >> c;
    std::cout << n - std::min({a, b, c}) << "\n";
}

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

---

B. Three Piles

题目大意

Alice 和 Bob 正在用三堆石子玩博弈游戏。初始时，Alice 拥有 $a$ 颗石子，Bob 拥有 $b$ 颗石子，第三堆公共石子堆中共有 $c$ 颗石子。

两人轮流行动，Alice 先手。在每个回合中，当前行动的玩家可以从第三堆石子中取走任意数量的石子（可以取 $0$ 颗），并将其累加到自己的石子堆中。如果双方在连续两个回合中均取了 $0$ 颗石子，游戏立即终止。

设游戏结束时 Alice 和 Bob 最终拥有的石子数分别为 $A$ 和 $B$，游戏的最终得分为 $|A-B|$。Alice 的目标是最大化得分，而 Bob 的目标是最小化得分。在双方均采取最优策略的前提下，求最终的游戏得分。

数据范围：

• 测试用例组数 $t$ 满足 $1\le t\le {10}^4$。

• 每堆石子的初始数量均满足 $0\le a,b,c\le {10}^9$。

---

思路

本题属于完全信息博弈中的极小化极大（Minimax）问题。Alice 追求差值绝对值 $|A-B|$ 的极大化，Bob 追求 $|A-B|$ 的极小化。

1. 策略一：Alice 首轮取尽公共石子

• 由于 Alice 拥有先手优势，且规则允许一次性取走任意数量的石子，Alice 可以在第 $1$ 回合直接取走第三堆全部的 $c$ 颗石子。
• 此时第三堆石子被清空（剩余数量为 $0$）。接下来的第 $2$ 回合 Bob 只能取 $0$ 颗；第 $3$ 回合 Alice 也只能取 $0$ 颗。连续两次取 $0$ 导致游戏强制终止。
• 此时双方最终石子数分别为 $A=a+c$ 和 $B=b$，最终得分为：

$$S_1=|a+c-b|$$

• 因为 Alice 可以单方面主动触发该分支，所以 Alice 保底可以获得不低于 $S_1$ 的收益。

2. 策略二：Alice 首轮取 $0$ 颗石子

• 若 Alice 在第 $1$ 回合选择取 $0$ 颗石子，此时轮到 Bob 行动：
• 若 Bob 同样选择取 $0$ 颗石子：构成连续两轮取 $0$，游戏立即结算，得分为：

$$S_2=|a-b|$$

• Bob 是否有动力取走 $y>0$ 颗石子？
• 当 $b\ge a$ 时，Bob 的石子数本身已不低于 Alice。若 Bob 取走 $y>0$ 颗石子，其持有量变为 $b+y$，与 Alice 现存的 $a$ 的差距被进一步拉大（$b+y-a>b-a$）。随后又将轮到 Alice 行动，Alice 可顺势收割剩余石子扩大分差。追求极小化分差的 Bob 绝不会选择使局面差距恶化的 $y>0$，其最优应对只能是同样取 $0$ 结束游戏，锁定得分 $S_2=|a-b|$。
• 当 $a>b$ 时，容易证明 $|a+c-b|=a+c-b\ge a-b=|a-b|$，即 $S_1\ge S_2$。此时 Alice 直接采取策略一即可获得更优结果，无须考虑此分支。

3. 博弈均衡解 Alice 在开局面临两种完全可控的路径选择：要么直接清空石子堆锁定 $|a+c-b|$，要么通过取 $0$ 迫使 Bob 接受当前初始差值 $|a-b|$。追求收益最大化的 Alice 必然会在两者之间取最大值：

$$\text{Score}=max(|a+c-b|,|a-b|)$$

---

复杂度分析

• 时间复杂度：对于每组测试用例，仅需执行常数次加减、绝对值计算与最值比较，单组用例时间复杂度为 $\mathcal{O}(1)$。处理全部 $t$ 组测试用例的总时间复杂度为 $\mathcal{O}(t)$。
• 空间复杂度：仅使用常数级别的标量变量存储输入与计算中间值，辅助空间复杂度为 $\mathcal{O}(1)$。

---

参考代码

参考代码

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

void fc() {
    int a, b, c;
    std::cin >> a >> b >> c;
 
    std::cout << std::max(std::abs(a + c - b), std::abs(a - b)) << "\n";
}

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

---

C. AND, OR, Sort!

题目大意

给定一个长度为 $n$ 的二进制字符串 $s$。允许执行以下操作任意次（可以为 $0$ 次）：

• 选择一个下标 $i$（$1\le i\le n$），并将 $s_i$ 替换为前缀 $s_1,s_2,\dots ,s_i$ 的按位与（bitwise AND）或按位或（bitwise OR）。

目标是通过最少的操作次数，使字符串 $s$ 按非递减顺序排序（即最终呈现形如 $00\dots 011\dots 1$ 的有序形式）。求所需的最少操作次数。

数据范围：

• 测试用例组数 $t$ 满足 $1\le t\le {10}^4$。

• 字符串长度 $n$ 满足 $2\le n\le 2\cdot {10}^5$。

• 所有测试用例的 $n$ 之和不超过 $2\cdot {10}^5$。

---

思路

本题的关键在于挖掘位运算操作的传递性与首位元素的不可变性。

1. 首元素的不可变性 当选取 $i=1$ 时，前缀仅包含元素 $s_1$ 本身。根据定义，单个元素的按位与及按位或均等于其自身。因此，$s_1$ 的取值在任何操作序列下均无法被更改。

2. 分类讨论：$s_1=1$ 的情形

• 由于 $s_1=1$ 且不可被修改，若要使整个序列非递减有序，所有后续位置 $s_2,\dots ,s_n$ 的最终取值必须全部为 $1$。
• 因为首位固定为 $1$，对于任意位置 $i\ge 2$，前缀 $s_1,\dots ,s_i$ 中必然存在 $1$，其前缀或恒为 $1$。
• 任何原先为 $0$ 的字符只需执行 $1$ 次前缀或操作即可变为 $1$；原本为 $1$ 的字符则无需改动。
• 因此，所需的最少操作次数即为原字符串中 $0$ 的总数，即：

$$\text{Cost}=n-\sum _{k=1}^n{s}_k$$

3. 分类讨论：$s_1=0$ 的情形

• 当首位为 $0$ 时，序列最终必然会被划分为两部分：前 $i$ 个字符均为 $0$，后 $n-i$ 个字符均为 $1$（其中分界点 $i$ 满足 $0\le i\le n$）。
• 置 $0$ 的可行性：因为 $s_1=0$，任何位置 $k\ge 2$ 的前缀中必然包含 $0$，其前缀与恒为 $0$。故任意原本为 $1$ 的位置均可通过 $1$ 次前缀与操作重置为 $0$。
• 置 $1$ 的可行性：一个位置要能变为 $1$，要求该位置之前（或当前位置）存在至少一个 $1$ 以提供前缀或的有效来源。
• 代价函数推导： 若选定分界点为 $i$（前 $i$ 个为 $0$，后 $n-i$ 个为 $1$）：
• 前缀区间 $[1,i]$ 中原有的 $1$ 需全部修改为 $0$，花费为该区间内 $1$ 的个数，即 $pre[i]$。
• 后缀区间 $[i+1,n]$ 中原有的 $0$ 需全部修改为 $1$，花费为该区间内 $0$ 的个数，即 $(n-i)-(pre[n]-pre[i])$。
• 目标代价为：

$$f(i)=pre[i]+(n-i-(pre[n]-pre[i]))$$

• 分界点合法性与单调性分析：
• 若原串不存在 $1$（全 $0$），则不可能凭空产生 $1$，序列只能保持全 $0$，对应 $i=n$ 时 $f(n)=0$，结果恒最优。
• 若原串存在 $1$，设首个 $1$ 出现的下标为 $p$。对于所有 $i<p$ 的分界点，前缀区间全为 $0$（$pre[i]=0$），代入公式得 $f(i)=n-i-pre[n]$。随着 $i$ 单调增加，该代价严格单调递减。因此在 $i<p$ 的无效区域内，代价函数单调递减，其最小值必然会在合法的 $i\ge p$ 区域内被更优解覆盖，不会导致非法状态被选取。
• 当 $i\ge p$ 时，前缀已覆盖了至少一个现存的 $1$。我们可先从左至右利用该 $1$ 通过前缀或操作把后缀的 $0$ 逐个置为 $1$；随后再利用 $s_1=0$ 通过前缀与操作将前缀中冗余的 $1$ 全部置为 $0$。该构造保证了上述代价上界严格可达。

因此，维护前缀和数组并在线性时间内枚举最优分界点 $i$ 取最小值即可。

---

复杂度分析

• 时间复杂度：构建前缀和数组需线性扫描原串，耗时 $\mathcal{O}(n)$；遍历分界点 $i\in [0,n]$ 进行常数时间的转移与比较，耗时 $\mathcal{O}(n)$。处理所有测试用例的总时间复杂度为 $\mathcal{O}(\sum n)=\mathcal{O}(N)$。

• 空间复杂度：需要一个大小为 $n+1$ 的动态数组 pre 记录前缀和信息，额外辅助空间复杂度为 $\mathcal{O}(n)$。

---

参考代码

参考代码

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

void fc() {
    int n;
    std::string s;
    std::cin >> n >> s;
 
    std::vector<int> pre(n + 1);
    for (int i = 0; i < n; i++) {
        pre[i + 1] = pre[i] + s[i] - '0';
    }
 
    if (s[0] == '1') {
        std::cout << n - pre[n] << '\n';
        return;
    }
 
    int ans = INT_MAX;
    for (int i = 0; i <= n; i++) { 
        ans = std::min(ans, pre[i] + n - i - (pre[n] - pre[i])); 
    }
    std::cout << ans << "\n";
}

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

---

D. Falling Concrete

题目大意

Vihaan 正在修补一条由 $n$ 个路段组成的道路，第 $i$ 个路段的初始高度为 $a_i$。

他拥有一辆叉车，可以执行以下操作任意次（可以为 $0$ 次）：

• 选择两个下标 $i,j$（满足 $1\le i<j\le n$），叉起第 $j$ 个路段并将其向后移至位置 $i$。

• 在搬运过程中，被搬运的路段每越过一个路段就会掉落 $1$ 个单位的混凝土到该路段上。随后，被搬运的路段插入到位置 $i$。

• 形式化地，子数组 $[a_i,a_{i+1},\dots ,a_{j-1},a_j]$ 会被替换为：

$$[a_j-(j-i),a_i+1,a_{i+1}+1,\dots ,a_{j-1}+1]$$

如果道路的某一部分是一个由若干高度相同的路段构成的连续区间，则称该部分是平坦的（flat）。求经过任意次操作后，道路中平坦部分的最大可能长度。

数据范围：

• 测试用例组数 $t$ 满足 $1\le t\le {10}^4$。

• 路段数量 $n$ 满足 $1\le n\le 2\cdot {10}^5$。

• 初始路段高度 $a_i$ 满足 $n\le a_i\le {10}^9$。

• 所有测试用例的 $n$ 之和不超过 $2\cdot {10}^5$。

• 题目保证在给定约束下，路段高度在任何操作序列下始终保持为正。

---

思路

1. 寻找操作不变量（Invariant） 采用 $0\text{-indexed}$ 坐标体系（即下标范围为 $0\le i<j<n$）考察单次操作：

• 原本位于位置 $j$ 的路段被移至位置 $i$，其高度变为 $a_j-(j-i)$。计算其高度与当前下标的差值：

$$(a_j-(j-i))-i=a_j-j$$

• 原本位于区间 $[i,j-1]$ 的任意路段 $k$，其位置右移至 $k+1$，高度变为 $a_k+1$。计算其高度与当前下标的差值：

$$(a_k+1)-(k+1)=a_k-k$$

这表明：对于任意一个路段，无论经过何种合法操作序列，其「当前高度与所在下标的差值」$b_k=a_k-k$ 恒定不变。

2. 置换自由度（可达性分析） 当选取 $j=i+1$ 时，操作将相邻的第 $i+1$ 个元素移至位置 $i$，原位置 $i$ 的元素顺延至位置 $i+1$。该操作完全等价于一次相邻对换（Adjacent Transposition）。 在代数学中，相邻对换是对称群 $S_n$ 的标准生成元集。因此，仅通过有限次相邻对换，即可在保持每个元素特征值 $b_k=a_k-k$ 不变的前提下，将所有路段任意重排为集合 $\{b_k\}$ 的任意排列。

3. 平坦区间的代数特征 设最终方案中存在一个起始下标为 $p$、长度为 $L$ 的平坦区间，区间内每个路段的高度均等于常数 $H$。 则对于该区间内的任意相对偏移量 $m$（$0\le m<L$），处于位置 $p+m$ 的路段其固有差值必须满足：

$$b_{p+m}^{\prime }=a_{p+m}-(p+m)=H-(p+m)=(H-p)-m$$

该式揭示了平坦区间的充分必要条件：

• 构成该平坦区间的 $L$ 个元素，其固有差值集合必须呈现为公差为 $1$ 的连续整数集合 $\{V,V-1,\dots ,V-(L-1)\}$（其中 $V=H-p$）。
• 由于下标 $p+m$ 严格递增，对应的差值 $b_{p+m}^{\prime }$ 必须严格递减，因此相同的差值在同一个平坦区间内至多只能被使用一次。

4. 问题转化与算法设计 问题最终等价于：在多重集 $\{a_i-i\mid 0\le i<n\}$ 中，寻找一个元素互不相同且数值严格连续的最大子集。

• 将每个位置的特征值计算为 $a_i\leftarrow a_i-i$；
• 对数组 $a$ 进行升序排序；
• 遍历排序后的序列，若遇到重复值则跳过（去重），若当前值等于前一个有效值加 $1$，则连续长度累加；否则重置计数器；
• 遍历过程中维护连续段的最大长度即可。

---

复杂度分析

• 时间复杂度：计算固有差值需要 $\mathcal{O}(n)$；对长度为 $n$ 的数组排序耗时 $\mathcal{O}(n\log n)$；一次线性扫描统计最长连续段耗时 $\mathcal{O}(n)$。对于全部测试用例，总时间复杂度为 $\mathcal{O}(\sum n\log n)$，在 $\sum n\le 2\cdot {10}^5$ 的限制下耗时远低于 2.0 秒的时限。

• 空间复杂度：使用大小为固定常数的全局静态数组存储元素，排序仅需递归栈开销 $\mathcal{O}(\log n)$，额外辅助空间复杂度为 $\mathcal{O}(1)$。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N=2e5+5;
int n;
int a[N];
void fc() {
    std::cin>>n;
    for(int i=0;i<n;i++)std::cin>>a[i],a[i]-=i;
    std::sort(a,a+n);

    int ans=0,c=1;
    for(int i=1;i<n;i++){
        if(a[i]==a[i-1])continue;
        if(a[i]==a[i-1]+1)c++;
        else {
            ans=std::max(ans,c);
            c=1;
        }
    }

    std::cout<<std::max(ans,c)<<"\n";
}

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

---

E. Prime Destruction

题目大意

给定一个由 $n$ 个正整数构成的多重集 $a$。允许执行以下操作任意次（可以为 $0$ 次）：

• 从多重集中选择一个大于 $1$ 的整数 $x$ 以及 $x$ 的一个质因数 $p$。将选取的该 $x$ 从多重集中移除，并向多重集中加入 $p$ 个数值为 $\frac{x}{p}$ 的整数。

同时给定一个正整数 $k$（$1\le k\le n$）。定义 $f(k)$ 为将多重集中的所有元素均削减至不超过 $k$ 所需的最少操作次数。求 $f(k)$ 的值。

数据范围：

• 测试用例组数 $t$ 满足 $1\le t\le {10}^4$。

• 多重集初始大小 $n$ 与目标上限 $k$ 满足 $1\le k\le n\le 2\cdot {10}^5$。

• 多重集中的元素 $a_i$ 满足 $1\le a_i\le n$。

• 所有测试用例的 $n$ 之和满足 $\sum n\le 2\cdot {10}^5$。

---

思路

1. 子问题独立性分析 每一次操作仅针对多重集中的单个数 $x$ 进行质因数拆分，所生成的 $p$ 个子元素 $\frac{x}{p}$ 之间以及与其他原有元素之间互不影响。因此，各个元素的拆分过程完全相互独立。 若定义 $cnt(x)$ 为将单个整数 $x$ 彻底拆分直至所有派生出的元素均满足 $\le k$ 所需的最少操作次数，则根据独立性原理，全局最少操作次数可转化为各元素独立贡献之和：

$$f(k)=\sum _{i=1}^{n}cnt(a_i)$$

2. 动态规划状态设计与转移方程

• 边界状态：若 $x\le k$，该数无需执行任何分解操作即已满足条件，因此：

$$cnt(x)=0(\mathrm{\forall }0\le x\le k)$$

• 状态转移：对于 $x>k$，必须对 $x$ 至少执行一次操作。
• 若枚举选取 $x$ 的某一质因数 $p$（满足 $p\mid x$ 且 $p\in \mathbb{P}$），当前操作消耗 $1$ 次。
• 产生的 $p$ 个子元素均为 $\frac{x}{p}$，后续为了使这 $p$ 个子元素均分解至不超过 $k$，每个分支均需消耗 $cnt\left(\frac{x}{p}\right)$ 次操作，共计 $p\cdot cnt\left(\frac{x}{p}\right)$ 次。
• 因此，选择质因数 $p$ 的总代价为 $1+p\cdot cnt\left(\frac{x}{p}\right)$。
• 为求得全局最优解，只需在 $x$ 的所有不同质因数中取最小值：

$$cnt(x)=\underset{\begin{array}{c}p\mid x\\ p\in \mathbb{P}\end{array}}{min}(1+p\cdot cnt\left(\frac{x}{p}\right))(\mathrm{\forall }k<x\le n)$$

3. 拓扑序与质因数快速分解

• 由于质数 $p\ge 2$，严格保证了 $\frac{x}{p}<x$。状态之间的转移关系构成一个天然的有向无环图（DAG），故 $x$ 按照从小到大的顺序从 $k+1$ 遍历至 $n$ 进行递推即可。
• 为了快速获取任意整数 $x$ 的所有互异质因数，可预先利用欧拉筛（线性筛）预处理出每个数的最小质因数 $minp[x]$。对于每个状态 $x$，借助 $minp$ 可在对数时间内完成质因数分解与转移。

---

复杂度分析

• 时间复杂度：

• 预处理阶段：欧拉筛在 $\mathcal{O}(N)$ 时间内求出 $N=2\cdot {10}^5$ 范围内的最小质因数。

• 单组测试阶段：DP 过程仅遍历区间 $[k+1,n]$，由于不超过 $2\cdot {10}^5$ 的整数其互异质因数个数 $\omega (x)\le 7$（因为前 $7$ 个质数之积 $2\times 3\times 5\times 7\times 11\times 13\times 17=510510>2\cdot {10}^5$），单点转移耗时为极小的常数级；统计答案仅需一次 $\mathcal{O}(n)$ 的求和。

• 处理所有测试用例的总时间复杂度为 $\mathcal{O}(N+\sum n)$，远低于 2.0 秒的时限。

• 空间复杂度：

• 线性筛数组 minp、素数存储 primes 以及 DP 数组 cnt 均采用全局静态空间，空间复杂度为 $\mathcal{O}(N)$。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N=2e5+5;
int k,n;
int a[N],minp[N];
ll cnt[N];
std::vector<int>primes;

// 线性筛预处理最小质因数 minp
void init() {
    for (int i = 2; i < N; ++i) {
        if (!minp[i]) {
            minp[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (i * p >= N) break;
            minp[i * p] = p;
            if (i % p == 0) break;
        }
    }
}

void fc() {
    std::cin>>n>>k;
    for(int i=1;i<=n;i++)std::cin>>a[i],cnt[i]=LLONG_MAX;
     
    for(int i=0;i<=k;i++)cnt[i]=0; 
    for(int i=k+1;i<=n;i++){
        ll base=2e9;
        ll temp=i;
        while(temp>1){
            ll p=minp[temp]; 
            base=std::min(base,1+p*cnt[i/p]); 
            while(temp%p==0)temp/=p;
        }
        cnt[i]=base;
    }
 
    ll ans=0;
    for(int i=1;i<=n;i++)ans+=cnt[a[i]];
    std::cout<<ans<<"\n";
}

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

---