3月27日刷题笔记——优先队列与中心扩展

今日用到的技巧#

懒惰删除（Lazy Deletion）#

Python 的 heapq 只能高效弹出堆顶元素 O(logN)。如果一个元素在最小堆里失效了，但它同时还在最大堆的中间位置，我们无法直接去最大堆里把它挖出来（强行挖取的时间复杂度是 O(N)）。

解法：准备一本状态注册表 deleted = [False] * n。当我们要从最大堆取元素时，先对照注册表看看堆顶元素是否已经失效。如果是失效的”幻影”，直接 heappop 扔掉，直到露出真正有效的数据为止。

TIP
懒惰删除的本质
不是真的删除元素，而是”标记作废 + 弹出时跳过”。代价是堆里会积累一些垃圾数据，但总量有上界（每个元素最多被标记一次），整体复杂度不变。

中心扩展基础法（Center Expansion）#

在处理回文变体（如左右两边字符集合完全一致）时，使用双指针向两边扩展是最直观、最稳妥的思路。每次扩展后，直接比较两边的频次数组是否相等即可。

WARNING
性能提示
直接使用 if countL == countR 在 Python 中会进行一次长度为 26 的数组比较。代码极其易读且不易出错，但在遇到极端超大数据（如十万级字符串）时，可能会出现超时（TLE）。适合作为考场保底方案。

题目一 · 反应堆过载防御（动态最值与懒惰删除）#

题目描述#

在一个生化反应堆中，最多只能安全容纳 $m$ 个能量核。现有 $n$ 个能量核依次按顺序被推入反应堆，第 $i$ 个能量核的初始稳定度为 $a_i$ 。

当反应堆内的能量核数量超过安全容量 $m$ 时，系统会触发过载防御机制：系统会强制排出当前反应堆内稳定度最高的那个能量核。强制排出操作会产生能量冲击，使得反应堆内所有剩余的能量核的稳定度降低 $x$ 点。如果某个能量核的稳定度降至 $0$ 或以下，它将自行湮灭并从反应堆中消失。

请问：在所有能量核处理完毕后，系统总共强制排出了多少个能量核？

审题思路#

拿到这道题，第一反应是”维护一个动态集合，随时取最大值”，自然想到最大堆。但问题在于两件事同时发生：

全场扣血：每次排出触发冲击波，所有存活核的稳定度都要减 $x$
稳定度归零自动湮灭：扣血后可能有核直接消失，需要及时感知

如果直接遍历堆里所有元素逐个扣血，复杂度爆炸。关键洞察是：不需要真的扣血，只需要记录”累计扣了多少”。每个核存入时记录登记稳定度 registered_hp = hp + total_damage，之后任何时刻该核的真实稳定度 = registered_hp - total_damage。这样全场扣血变成只更新一个全局变量。

湮灭检测用最小堆解决：最小堆堆顶始终是登记稳定度最低的核，只要 堆顶 <= total_damage，说明真实稳定度 ≤ 0，已经湮灭。两个堆同步维护同一批核，用 deleted 数组做懒惰删除保持一致性。

CAUTION
操作顺序很关键
每轮流程必须是：入堆 → 清理湮灭 → 判断超载 → 排出最稳定核 → 触发冲击波 → 再次清理湮灭。
特别是”入堆后先清理再判超载”这一步容易漏：新核入场可能恰好触发冲击波让其他核湮灭，如果不先清理就判超载，会产生”假超载”（以为超了 m 个但实际上已经有核湮灭了）。

核心思路#

典型的 贪心 + 双优先队列（双堆）+ 懒惰删除。

维护一个最小堆（随时监测谁的稳定度归零了）和一个最大堆（用于寻找最稳定的能量核排出）
每次有新能量核入堆后，先进行”清理”（因为可能有残血核刚好被之前的冲击波震碎，腾出位置）
如果容量超载（alive_cnt > m），从最大堆抓出最稳定的核排出
排出触发冲击波（total_damage += x），全场扣除稳定度，紧接着再次执行”清理”

代码#

1
import sys
2
import heapq
3

4
def solve():
5
    input_data = sys.stdin.read().split()
6
    if not input_data: return
7

8
    n = int(input_data[0])
9
    m = int(input_data[1])
10
    x = int(input_data[2])
11
    a = [int(v) for v in input_data[3:]]
12

13
    min_heap = []
14
    max_heap = []
15
    deleted = [False] * n
16

17
    alive_cnt = 0
18
    total_damage = 0
19
    res = 0
20

21
    def clean_reactor():
22
        nonlocal alive_cnt
23
        # 只要最弱的核的登记稳定度 <= 累计冲击波伤害，说明其真实稳定度 <= 0
24
        while min_heap and min_heap[0][0] <= total_damage:
25
            _, dead_idx = heapq.heappop(min_heap)
26
            if not deleted[dead_idx]:
27
                deleted[dead_idx] = True
28
                alive_cnt -= 1
29

30
    for i in range(n):
31
        hp = a[i]
32
        registered_hp = hp + total_damage
33

34
        # 存入双堆，Python默认小顶堆，存最大堆要加负号
35
        heapq.heappush(min_heap, (registered_hp, i))
36
        heapq.heappush(max_heap, (-registered_hp, i))
37
        alive_cnt += 1
38

39
        clean_reactor()  # 入场先清理，防止"假超载"
40

41
        # 超载防御判定
42
        if alive_cnt > m:
43
            # 过滤掉最大堆顶部的"湮灭幻影"
44
            while max_heap and deleted[max_heap[0][1]]:
45
                heapq.heappop(max_heap)
46

47
            _, target_idx = heapq.heappop(max_heap)
48
            deleted[target_idx] = True
49
            alive_cnt -= 1
50
            res += 1
51

52
            total_damage += x   # 触发全场冲击波
53
            clean_reactor()     # 冲击波后二次清理
54

55
    print(res)
56

57
if __name__ == "__main__":
58
    solve()

IMPORTANT
registered_hp 的设计思路
每个核存入堆时记录的是 hp + total_damage（登记稳定度），而不是真实稳定度。这样全场扣血时不需要遍历堆里所有元素，只需要更新 total_damage。判断时用 登记稳定度 - total_damage 还原真实稳定度，或直接用 登记稳定度 <= total_damage 判断是否湮灭。

题目二 · 拦截信号解码（中心扩展基础版）#

题目描述#

情报部门截获了一段由小写字母 a-z 组成的敌方密文信号。密码专家定义了一种”伪回文”信号段：如果以某个位置为中心，其左半部分的字符集合和右半部分的字符集合完全一致（即左半边是右半边的字母异位词），那么这段信号就被认为是有效解码段。

给定截获的信号字符串，请计算其中包含多少个有效解码段。

审题思路#

这道题的核心难点是”异位词判断”而不是”回文判断”。普通回文要求左右镜像对称，而这道题只要求左右字符集合相同（各字符出现次数一致即可，顺序无所谓）。

暴力枚举所有子串然后判断异位词是 O(N³)，太慢。关键观察是：以同一个点为中心，向外扩展时可以增量更新频次数组，不需要每次重新统计。每扩展一步只是给左右各新增一个字符，O(1) 更新，然后 O(26) 比较，整体 O(26N²) 可以接受。

CAUTION
奇偶中心都要枚举
scan(i-1, i+1) 处理奇数长度（以 s[i] 为中心），scan(i, i+1) 处理偶数长度（以 s[i] 和 s[i+1] 之间为中心）。两个都要调用，漏掉偶数中心会少算很多结果。

核心思路#

使用最直观的 中心扩展法。

遍历字符串的每一个字符，将其作为中心点
每次同时向左和向右扩展一位，分别统计左半部分和右半部分的字符频次
直接对比左右两个频次数组（countL == countR），如果相等，说明找到了一个有效解码段

代码#

1
import sys
2

3
def solve():
4
    # 务必使用 strip() 去除末尾的换行符
5
    s = sys.stdin.read().strip()
6
    if not s:
7
        return
8

9
    n = len(s)
10
    res = 0
11

12
    # 基础中心扩展函数
13
    def scan(left: int, right: int) -> int:
14
        countL = [0] * 26
15
        countR = [0] * 26
16
        count = 0
17

18
        while left >= 0 and right < n:
19
            # 分别记录左右两边新增的字符
20
            countL[ord(s[left]) - ord('a')] += 1
21
            countR[ord(s[right]) - ord('a')] += 1
22

23
            # 直接比较两个列表是否完全一致
24
            if countL == countR:
25
                count += 1
26

27
            left -= 1
28
            right += 1
29

30
        return count
31

32
    # 主循环：遍历每一个可能的回文中心
33
    for i in range(n):
34
        res += 1               # 单个字符本身也算一个有效段
35
        res += scan(i-1, i+1)  # 奇数长度中心扩展
36
        res += scan(i, i+1)    # 偶数长度中心扩展
37

38
    print(res)
39

40
if __name__ == "__main__":
41
    solve()

NOTE
countL[ord(s[left]) - ord('a')] += 1 是什么意思
这行代码的作用是把字符映射成 0-25 的下标，存入频次数组。
ord(s[left]) 获取字符的 ASCII 码，比如 'a' 是 97，'c' 是 99。减去 ord('a')（即 97）之后，'a' → 0，'b' → 1，'c' → 2，以此类推，26 个字母刚好对应下标 0-25。
举例：
1
s = "acb"
2
# left = 2，s[left] = 'b'
3
ord('b') - ord('a')  # = 98 - 97 = 1
4
countL[1] += 1       # 下标 1 代表字母 'b'，出现次数 +1
所以 countL[i] 表示左半部分第 i 个字母（chr(i + ord('a'))）出现的次数。countR 同理统计右半部分。

TIP
为什么单个字符也算一个有效段
单个字符的左半部分和右半部分都是空集，空集 == 空集，满足条件，所以每个字符本身计 1 个。

NOTE
如果遇到 TLE 怎么办
保底方案超时时，可以用差分数组优化：维护一个 diff[26] 数组，diff[c] += 1 表示左边比右边多一个字符 c，diff[c] -= 1 表示右边多一个。当 diff 全为零时左右相等。这样比较从 O(26) 降到 O(1)（只需维护一个”非零计数器”），整体降到 O(N²)。