非官方|ACGO巅峰赛#31题解

（没罐头了awa，看看能不能获奖www）

气死了，这次比赛原本第一名的，然后被踹到第六名了www

本人只是一个刚注册半年之久的蒟蒻，如果本文有啥不对的地方，欢迎各位dalao支指出！

食用须知：

• 首先，为了更好的帮助各位，题解里面不用万能头（好叭其实也是我的码风）
• 所有代码皆为我自己的马蜂，r如果看不惯，请见谅

下面正文开始：

竞赛大致康康

首先，本次比赛的难度啊，如下（hhh），选手们可以借此评估一下自身的技术水平：
题库真是个好东西awa

题目编号	题目难度	标题
T1	雾港城的神秘区域	入门
T2	雾港城的符文	普及-
T3	雾港学宫的括号匹配	普及/提高-
T4	雾港实验室的高压服务器	普及/提高-
T5	雾港冲刺营的队伍序列	普及/提高-
T6	雾港实验室的神秘联通块	普及+/提高

---

T1 雾港城的神秘区域

题目大意

给定一棵包含n个节点的树，其中k个两两不同的节点安装了信标。你需要删除最少的边，将树划分为若干个互不连通的辖区，要求每个辖区内的信标数量不超过1。请输出最少需要删除的边数。

解题思路

1. 下界分析（最少需要删除的边数）
   要满足每个辖区最多1个信标的要求，k个信标必须分别位于k个不同的辖区中。
   树的初始状态是1个连通块，每删除1条边，连通块的数量恰好增加1。因此，要从1个连通块得到k个连通块，至少需要删除k-1条边。

2. 可行性证明（k-1条边一定可以满足要求）
   对于任意的树结构和任意k个信标位置，我们都可以通过删除k-1条边完成划分：
   每次选择两个位于同一连通块的信标，删除它们之间唯一路径上的任意一条边，即可将这两个信标分到不同的连通块中。重复该操作k-1次，就能将k个信标全部分到不同的连通块中，完全满足题目要求。

3. 特殊情况处理

• 当k=0（没有信标）时，无需删除任何边，答案为0；
• 当k=1时，仅需1个连通块，无需删除边，答案为0。
  以上情况均可通过 max(0, k-1) 统一计算。

代码逻辑讲解

代码完全基于上述结论实现：

• 读取输入的n和k；
• 依次读取k个信标节点和n-1条树边（仅完成输入读取，无需存储，因为答案与这些数据无关，仅为了避免输入流错位）；
• 直接计算并输出 max(0, k-1) ，即为最少需要删除的边数。

参考代码

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < k; ++i) {
        int a;
        cin >> a;
    }
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
    }
    cout << max(0, k - 1) << '\n';
    return 0;
}

---

（啊，下面的题目我会讲的详细一点好叭）

T2 雾港城的符文

题目大意

给定一个仅由小写字母组成的字符串  $s$ ，每次可以删除一个字符，要求删除后得到的新字符串  $t$  中不存在任何长度$≥2$的回文子串，求最少需要删除的字符个数。

解题思路

核心约束分析

首先明确：不存在长度$≥2$的回文子串的字符串，必须满足两个核心条件：

• 无相邻相同字符：避免出现长度为2的回文（如 aa）；
• 无间隔一位的相同字符：避免出现长度为3的回文（如 aba ）。

对于长度$≥4$的回文子串，其必然包含长度为2或3的回文子串（例如 abba 包含相邻相同的 bb ， abcba 包含长度3的 bcb ）。因此只要满足上述两个条件，就能完全杜绝所有长度≥2的回文子串。

策略推导

最少删除次数等价于保留最长的符合上述约束的子序列（删除字符后剩余字符相对顺序不变，对应原字符串的子序列）。

这里采用贪心策略：遍历原字符串的每个字符，只要当前字符可以加入已保留的序列（即与已保留序列的最后一个、倒数第二个字符都不相等），就保留该字符；否则删除。

贪心说明：对于每个符合条件的字符，保留它不会缩小后续的选择空间，反而能最大化保留的字符数，因此可以得到全局最优解。

参考代码

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    int a = 0, b = 0, cnt = 0;
    for (int i = 0; i < n; ++i) {
        char c = s[i];
        if (cnt == 0) {
            a = c;
            cnt = 1;
        } else if (cnt == 1) {
            if (c != a) {
                b = a;
                a = c;
                cnt = 2;
            }
        } else {
            if (c != a && c != b) {
                b = a;
                a = c;
                cnt++;
            }
        }
    }
    cout << n - cnt << endl;
    return 0;
}

---

T3 雾港学宫的括号匹配

题目大意

给定一个仅由  (  和  )  组成的字符串，你可以删除任意数量的字符（剩余字符保持原有相对顺序），要求最终得到的字符串是合法括号串。请你求出最少需要删除的字符个数。

合法括号串的定义：

• 空串是合法括号串；
• 若  A 是合法括号串，则  (A)  也是合法括号串；
• 若  A 、 B  是合法括号串，则  AB  也是合法括号串。
  通俗来说，合法括号串需要满足：左括号与右括号总数相等，且任意前缀中左括号的数量不少于右括号的数量。

解题思路

核心策略

贪心算法
要让删除次数最少，等价于尽可能多地保留能成功配对的括号，因此采用贪心策略遍历字符串，每一步都做出当前最优的选择，最终得到全局最优解。

贪心的核心逻辑：
1. 遍历字符串时，遇到左括号  (  先暂时保留，因为它可以和后续的右括号配对；
2. 遇到右括号  )  时，若当前有未配对的左括号，就用这个右括号完成一次配对（两个括号都保留）；若没有未配对的左括号，这个右括号无法形成合法配对，必须删除；
3. 遍历结束后，剩余的未配对左括号，没有后续的右括号可以与之配对，也必须全部删除。

贪心说明：合法括号串的配对具有严格的顺序性，右括号只能和它之前的左括号配对。我们的策略在遍历过程中，尽可能完成了所有能完成的配对，没有浪费任何一个可以配对的右括号，最终保留的配对数是最大的，因此删除次数必然是最少的。

满足：左括号与右括号总数相等，且任意前缀中左括号的数量不少于右括号的数量。

代码逻辑讲解

代码完全基于上述贪心策略实现，变量定义如下：

• a ：记录当前遍历过程中，未完成配对的左括号数量（即可用于后续配对的左括号数）；
• b ：记录遍历过程中，已经确定必须删除的字符数量。

遍历字符串的每个字符，分两种情况处理：

1. 若当前字符是  ( ：将  a  加1，暂时保留这个左括号，等待后续右括号配对。
2. 若当前字符是  ) ：

• 若  a > 0 ：说明有可配对的左括号，将  a  减1，完成一次配对，两个括号都保留，无需删除；
• 若  a == 0 ：说明没有可配对的左括号，这个右括号必须删除，将  b  加1。

遍历完成后， a  中存储的是遍历结束后仍未配对的左括号，这些左括号无法完成配对，必须全部删除，因此将  a  的值加到  b  中。最终  b  的值就是最少需要删除的字符总数。

参考代码

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    int a = 0, b = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '(') {
            a++;
        } else {
            if (a > 0) {
                a--;
            } else {
                b++;
            }
        }
    }
    b += a;
    cout << b << endl;
    return 0;
}

---

（好的，我的任务完成了，hhh，但是出于良心，我打算把后面的题目讲完）

T4 雾港实验室的高压服务器

题目大意

有n个初始运行在数据中心A的任务，每个任务的运行时间为闭区间 [li, ri] 。你可以在任意时刻t，迁移若干个此刻正在A上运行的任务到数据中心B，迁移瞬时完成，任务运行区间不变，且迁移后不可返回A，最多可迁移K个任务。

定义时刻t A的压力为该时刻仍在A上运行的任务数量，要求设计迁移方案，使得整个时间轴上A的最大压力（峰值压力）尽可能小，输出这个最小的峰值压力。

解题思路

本题是典型的最小化最大值问题，核心解法为二分答案 + 贪心验证，整体思路如下：

二分答案的可行性

峰值压力的取值具有单调性：

• 若峰值p可行（即存在迁移方案，用不超过K次迁移让A的峰值不超过p），则所有大于p的峰值必然都可行（约束更宽松）；
• 若峰值p不可行，则所有小于p的峰值也必然不可行。

因此我们可以二分峰值p的范围（左边界0，右边界n），找到最小的可行p。

贪心验证策略

对于给定的峰值p，我们需要判断能否通过不超过K次迁移，让A的峰值始终不超过p。这里采用贪心策略，核心逻辑是按时间顺序处理任务，优先保留结束时间早的任务，迁移结束时间最晚的任务，以最小化总迁移次数。

贪心的正确性说明：
当A上的任务数超过p时，必须迁移部分任务。迁移结束时间最晚的任务，能最大程度减少该任务对后续时间的资源占用，避免未来出现更多的任务重叠，从而最小化总迁移次数，是当前最优的局部选择，最终能得到全局最优解。

验证流程

1. 预处理：将所有任务按左端点 li 升序排序，按任务开始的时间顺序处理。
2. 维护有序集合：用有序集合存储当前留在A上的任务的结束时间 ri ，方便快速获取最早结束和最晚结束的任务。
3. 遍历处理每个任务：

• 清理已结束的任务：将集合中结束时间$≤$当前任务左端点 li 的任务全部移除（这些任务已运行结束，不再占用A的资源）。
• 将当前任务加入A，插入其结束时间到集合中。
• 若当前A上的任务数超过p，循环移除集合中结束时间最晚的任务（即迁移该任务），统计迁移次数，若迁移次数超过K则直接判定p不可行。

4. 遍历完成后，若总迁移次数$≤K$，则p可行，否则不可行。

代码逻辑讲解

代码完全基于上述思路实现，各部分逻辑如下：

主函数

1. 读取输入的n、K，以及每个任务的 li 和 ri ，存储为 pair<int, int> 类型的数组，默认按 li 升序排序。
2. 初始化二分边界：左边界 l=0 ，右边界 r=n ，初始答案 ans=n 。
3. 二分循环：每次取中间值 mid 作为当前尝试的峰值p，调用 f(mid) 判断是否可行。

• 若可行：更新答案 ans=mid ，并尝试更小的峰值，将右边界 r=mid-1 。
• 若不可行：需要更大的峰值，将左边界 l=mid+1 。
  4. 二分结束后，输出最小的可行峰值 ans 。

验证函数  bool f(int p)

1. 边界处理：若 p=0 ，需要将所有任务迁移到B，直接返回 k>=n 。
2. 定义 multiset<int> m ：有序存储当前留在A上的任务的结束时间，支持重复元素，默认升序排列。
3. 定义 int c=0 ：统计已迁移的任务数量。
4. 遍历每个任务：

• 获取当前任务的左端点 L=li 、右端点 R=ri 。
• 清理已结束任务：循环删除集合中最小的元素（最早结束的任务），直到集合为空或最小元素大于 L 。
• 将当前任务的结束时间 R 插入集合，默认留在A上。
• 若集合大小超过p：循环删除集合中最大的元素（最晚结束的任务），每删除一次迁移次数 c 加$1$，若 c>k 直接返回 false ，直到集合大小$≤p$。
  5. 遍历完成后，返回 c<=k ，判断是否满足迁移次数限制。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int n, k;
vector<pair<int, int>> a;

bool chk(int x) {
    multiset<int> s;
    int c = 0;
    for (auto &t : a) {
        int l = t.first, r = t.second;
        while (!s.empty() && *s.begin() < l) s.erase(s.begin());
        s.insert(r);
        if (s.size() > x) {
            s.erase(--s.end());
            c++;
            if (c > k) return 0;
        }
    }
    return c <= k;
}

int main() {
    scanf("%d%d", &n, &k);
    a.resize(n);
    for (int i = 0; i < n; i++) scanf("%d%d", &a[i].first, &a[i].second);
    sort(a.begin(), a.end());
    int l = 0, r = n, ans = n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (chk(mid)) {
            ans = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    printf("%d\n", ans);
    return 0;
}

---

T5 雾港冲刺营的队伍序列

题目大意

你有一个长度为n的昵称字符串S，仅包含小写字母。你可以对昵称进行修改，规则如下：
1. 只能将字符改小（如 d→c ，不能反向修改）；
2. 最多修改K个不同的位置，同一位置无论修改多少位，仅计1次修改；
3. 修改第i位的花费为 (原字符-新字符)×p[i] ，总花费不能超过B。

修改完成后，所有报名者的昵称按字典序从小到大排序，同名者按报名先后排序（你报名最晚，同名时排在最后）。你的目标是让自己的名次尽可能小，若有多个方案能达到相同的最小名次，输出其中字典序最小的最终昵称。

解题思路

核心逻辑转化

名次的核心决定因素是你最终昵称的字典序：昵称的字典序越小，排序越靠前，名次就越小。同时题目要求同名次下输出字典序最小的昵称，因此问题的核心转化为：在修改规则的约束下，生成字典序最小的字符串。

贪心策略（生成最小字典序字符串）

字典序的比较规则是从左到右优先匹配，左侧字符的优先级远高于右侧。因此要得到最小字典序的字符串，必须采用从左到右、逐位尽可能改到最小的贪心策略：

1. 从左到右遍历每个字符，优先修改左侧的字符，因为左侧字符对字典序的影响最大；
2. 对于当前位置，只要还有剩余修改次数和预算，就将字符改到能达到的最小值（优先改到 a，若预算不足则改到预算允许的最小值）；
3. 一旦修改次数用尽或预算花完，直接停止修改，后续字符保持原样。

名次计算

1. 将其他所有人的昵称按字典序排序；
2. 用二分查找找到第一个比你的最终昵称大的位置，该位置的索引就是所有字典序小于等于你的昵称的人数；
3. 你的名次为该索引+1（因为同名时你排在最后）。

代码逻辑讲解

代码完全基于上述贪心策略实现，各部分逻辑如下：
1. 输入处理：读取n、m、K、B，原字符串s，其他m个人的昵称数组a，以及每个位置的修改单价数组p。注意使用 long long 类型存储花费相关变量，避免溢出（B最大为1e18）。
2. 贪心生成最小字典序昵称：
1.初始化最终昵称 t 为原字符串 s ，剩余修改次数 r=K ，剩余预算 c=B。
2.从左到右遍历每个字符：

• 若剩余修改次数 r=0或剩余预算 c=0 ，直接停止遍历，后续字符无需修改。
• 若当前字符已经是 a （无法再改小），跳过当前位置。
• 计算当前位置最多能修改的位数：预算允许的最大修改位数 mx = c / p[i] ，以及字符能改到 a 的最大位数 now （当前字符的数值， a=0 ），取两者的最小值 d 。
• 若 d=0 （预算不足以修改1位），跳过当前位置。
• 修改当前字符为 'a' + now - d ，扣除对应花费 d*p[i] ，剩余修改次数 r 减1。
  3. 计算名次：
• 将其他所有人的昵称数组 a 按字典序排序。
• 使用 upper_bound 找到数组中第一个大于 t 的元素的迭代器，其索引 e 即为所有字典序小于等于 t 的人数。
• 最终名次为 e + 1 （同名时你排在最后）。

4. 输出结果：打印名次和最终的昵称 t 。

参考代码

#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int n, m, k;
    long long b;
    scanf("%d%d%d%lld", &n, &m, &k, &b);
    char buf[200005];
    scanf("%s", buf);
    string s = buf;
    vector<string> a(m);
    for (int i = 0; i < m; ++i) {
        scanf("%s", buf);
        a[i] = buf;
    }
    vector<long long> p(n);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &p[i]);
    }
    string t = s;
    int r = k;
    long long c = b;
    for (int i = 0; i < n && r > 0 && c > 0; ++i) {
        int now = s[i] - 'a';
        if (now == 0) continue;
        long long mx = c / p[i];
        if (mx == 0) continue;
        long long d = min((long long)now, mx);
        t[i] = 'a' + now - d;
        c -= d * p[i];
        r--;
    }
    sort(a.begin(), a.end());
    int e = upper_bound(a.begin(), a.end(), t) - a.begin();
    printf("%d\n", e + 1);
    printf("%s\n", t.c_str());
    return 0;
}

---

（已经有点力不从心了www，快不行了，下面的是我第二天完成的awa）

T6 雾港实验室的神秘联通块

题目大意

初始有$n$个孤立的终端，按时间顺序进行$m$次加边操作，每次添加一条永久存在的无向边。有$q$个询问，每个询问给出两个终端$u$和$v$，求最早在第几次操作后，u和v能够连通；若$m$次操作后仍不连通，输出-1。特别地，当$u=v$时，答案为0（初始状态就连通）。

解题思路

本题是经典的动态连通性离线查询问题，核心解法为带启发式合并（按秩合并）的并查集 + 离线处理询问，整体思路如下：

1. 离线处理的核心逻辑
   由于所有加边操作和询问都是提前已知的，无需在线实时响应，因此我们可以先存储所有询问，再按时间顺序逐步加边，在合并连通块的过程中，同步处理相关询问，记录答案。

2. 并查集的启发式合并
   并查集用于维护终端的连通性，同时采用启发式合并（小连通块合并到大连通块），保证每个点最多被遍历O(logn)次，从而控制总时间复杂度。

3. 询问的处理策略

• 预处理：将每个询问分别存储到其两个端点的询问列表中，方便后续在连通块合并时快速查询。
• 合并时处理询问：当合并两个连通块时，遍历较小连通块中的所有点，检查该点的所有未处理询问。若询问的另一个端点已经在较大的连通块中，说明本次合并让两个端点首次连通，此时记录当前的操作编号为该询问的答案，并标记询问已处理，避免重复计算。

4. 边界处理

• 当u=v时，直接标记答案为0，无需后续处理。
• 所有操作完成后，仍未被处理的询问，说明两个端点始终不连通，答案为-1。

代码逻辑讲解

代码完全基于上述思路实现，各部分逻辑如下：
首先：变量与数据结构定义

• f[] ：并查集的父节点数组， find(x) 函数用于查询x的根节点，带路径压缩优化。
• s[] ：记录每个连通块的大小，用于启发式合并。
• vec[] ：每个连通块对应的点列表， vec[root] 存储以root为根的连通块中的所有点。
• q[] ：每个点对应的询问列表， q[u] 存储所有包含u的询问的编号。
• x[] 、 y[] ：存储每个询问的两个端点。
• ans[] ：存储每个询问的答案，初始值为-1。
• vis[] ：标记询问是否已被处理，避免重复计算。
• e[] ：存储m次加边操作的两个端点。

然后：输入与初始化
1. 读取n、m、q（代码中用 qn 表示询问数量，避免与数组 q[] 重名）。
2. 读取m条边，存入 e[] 数组。
3. 读取q个询问：

• 若u==v，直接设置 ans[i]=0 ，并标记 vis[i]=1 （已处理）。
• 否则，将询问编号i分别加入 q[u] 和 q[v] ，方便后续查询。
  4. 并查集初始化：每个点的父节点为自身，连通块大小为1， vec[i] 中仅包含点i。

接着：按时间顺序加边与合并处理
遍历每条边（t从0到m-1，对应第t+1次操作）：
1. 找到当前边两个端点的根 fu 和 fv ，若已连通则跳过。
2. 合并：保证 fu 是较大连通块的根， fv 是较小连通块的根，否则交换两者。
3. 遍历较小连通块 fv 中的所有点p：

• 遍历p的所有询问编号id，若询问未被处理（ vis[id]==0 ），找到该询问的另一个端点o。
• 若o的根等于 fu （即o在较大的连通块中），说明本次合并让p和o首次连通，设置 ans[id] = t+1 ，并标记 vis[id]=1 。
• 将点p加入较大连通块 fu 的 vec 列表中。

4. 清空较小连通块 fv 的 vec 列表，合并父节点 f[fv]=fu ，更新连通块大小 s[fu] += s[fv] 。

最后：输出结果
遍历所有询问的 ans数组，按顺序输出每个询问的答案。

参考代码

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 200010;
int f[N], s[N];
vector<int> vec[N], q[N];
int x[N], y[N], ans[N];
bool vis[N];
pair<int, int> e[N];
int n, m, qn;

int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}

int main() {
    scanf("%d%d%d", &n, &m, &qn);
    for (int i = 0; i < m; ++i) {
        scanf("%d%d", &e[i].first, &e[i].second);
    }
    for (int i = 0; i < qn; ++i) {
        scanf("%d%d", &x[i], &y[i]);
        if (x[i] == y[i]) {
            ans[i] = 0;
            vis[i] = 1;
        } else {
            ans[i] = -1;
            vis[i] = 0;
            q[x[i]].push_back(i);
            q[y[i]].push_back(i);
        }
    }
    for (int i = 1; i <= n; ++i) {
        f[i] = i;
        s[i] = 1;
        vec[i].push_back(i);
    }
    for (int t = 0; t < m; ++t) {
        int u = e[t].first, v = e[t].second;
        int fu = find(u), fv = find(v);
        if (fu == fv) continue;
        if (s[fu] < s[fv]) swap(fu, fv);
        for (int p : vec[fv]) {
            for (int id : q[p]) {
                if (vis[id]) continue;
                int o = x[id] == p ? y[id] : x[id];
                if (find(o) == fu) {
                    ans[id] = t + 1;
                    vis[id] = 1;
                }
            }
            vec[fu].push_back(p);
        }
        vec[fv].clear();
        f[fv] = fu;
        s[fu] += s[fv];
    }
    for (int i = 0; i < qn; ++i) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

---

有一个细节问题，就是题库中T6的通过率竟然比T5高

好了，题解到这里就写完了。@AC君我真的很需要罐头！awa

非常感谢：@你是不是不喜欢c++在我发布初版的时候告诉我T1不是巅峰赛的题解（我也不知道当时咋回事awa）

写完以后才发现给笔记本不是罐头（也刑叭）