巅峰赛31题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 雾港城的神秘区域 入门 T2 雾港城的符文 普及 - T3 雾港学宫的括号匹配 普及/提高- T4 雾港实验室的高压服务器 普及/提高- T5 雾港冲刺营的队伍序列 普及+/提高 T6 雾港实验室的神秘联通块 普及+/提高
T1
简要题解
关键只看信标数 k：删一条边会让连通块数量从 1 变成 2，再删一条变成 3，总之删 x 条边就会得到 x+1 个连通块。要求每块信标数 ≤1，若有 k 个信标，就至少需要 k 个连通块来“装下”它们，所以必须有 x+1≥k，也就是 x≥k−1；另一方面总能做到 k−1：把所有信标连起来的最小连通子树里，信标一定出现在叶子上，反复把一个叶子信标与子树内部相连的那条边切断，就能一次分离出一个只含 1 个信标的连通块，做 k−1 次即可把所有信标分到不同块里。于是答案就是 max(0, k−1)。
参考代码
T2
简要题解
任何长度 ≥4 的回文子串内部一定会包含一个长度为 2 的回文（相邻相等）或者长度为 3 的回文（形如 aba），所以只要把长度 2 和 3 的回文都挡住，就不会出现更长的回文。于是从左到右贪心构造保留下来的串 t：依次尝试把当前字符加到 t 末尾，如果会造成 t 的最后两位相等，或最后三位形成回文，就删掉这个字符；否则保留。这样每次只在“当前字符一加就必然违规”的情况下才删除，而且违规只可能由最新加入的字符触发，因此这个贪心的删除次数就是最少的，整体 O(n)。
参考代码
T3
简要题解
从左到右扫描字符串，用 bal 记录当前还没被匹配的左括号数量。遇到 '(' 就 bal++；遇到 ')' 时如果 bal>0 说明能和之前某个 '(' 配对，就 bal--，否则这个 ')' 无论如何都配不到，只能删除，答案加一。扫描结束后 bal 还剩多少，表示有多少个 '(' 没法被匹配，只能删掉它们，所以答案再加上 bal。
参考代码
T4
简要题解
迁移发生在什么时候其实不重要：如果某个任务打算在区间中间才迁走，把它改成在 l_i 一开始就迁走只会让 A 的压力更小，不会变大，所以等价于“直接选出至多 K 个区间整段不留在 A 上”。于是问题变成删掉至多 K 个区间，让剩余区间的最大重叠数最小。我们二分答案 X，判定是否能把最大重叠压到 ≤X：按 l 从小到大扫一遍，用 multiset 维护当前还没结束的右端点集合（右端点 < 当前 l 的就删掉），每插入一个新区间后如果集合大小变成 X+1，说明此时必须删掉一个区间才能不超限，贪心删右端点最大的那个（它拖得最久，最容易影响后面），统计最少删掉的数量是否 ≤K。二分最小可行的 X
即答案。
参考代码
T5
简要题解
要让名次尽量小，只需要让自己的最终昵称字典序尽量小，因为当昵称变得更小的时候，队伍里“小于等于它”的人数只会减少，不可能增加，所以名次是单调变好的。于是从左到右处理自己的字符串，高位比低位重要：只要还能动手并且预算够把当前位置至少降低 1 位，就应该立刻动这个位置，否则再怎么改后面都无法在字典序上超过“把更靠左的位置变小”。并且一旦决定改某个位置，为了让字典序尽可能小，当然应当在不超过预算的前提下把它尽量降到更小（同一位置降得更小不会额外消耗动手次数）。因此对每个位置 i 计算最多能降低的位数 delta=min(S[i]-'a', B/p_i)，若 delta>0 就把字符减去
delta、扣除 delta*p_i，并把可修改位置数 K 减 1。得到最终昵称 T 后，将其他人的昵称排序，用 upper_bound(T) 统计有多少昵称字典序小于等于 T（同名也算在前面，因为你报名最晚），名次就是这个数量加 1。
参考代码
T6
简要题解
把每条询问的答案看成在 [1,m][1,m][1,m] 上的一个“最早满足”的位置。连通性具有单调性：若在时刻 ttt 已经连通，那么在任意 t′>tt'>tt′>t 也一定连通，因此每个询问都可以二分答案。为了避免对每个询问都单独重建并查集，把所有询问的二分过程并行起来：每一轮对仍未确定的询问取中点 midmidmid 分桶，然后按 midmidmid 从小到大推进时间指针，依次把前 midmidmid 条边用并查集合并，在对应桶里判断这些询问是否连通，从而收缩各自的二分区间。重复约 logm\log mlogm 轮后区间收敛得到最早连通时刻；若收敛到 m+1m+1m+1
则表示直到最后也不连通输出 −1-1−1，另外 u=vu=vu=v 的询问直接输出 000。
参考代码
