四道题拆解AtCoder 458：从字符串切片到双堆维护中位数

2秒时限、1024MB内存，四道题分值从100点到400点递增。这是AtCoder Beginner Contest 458（SMBC编程竞赛#1）的A到D题，表面看是常规算法练习，实际藏着几道值得细品的实现陷阱。

本文整理参赛时的解题思路与Python代码，重点复盘那些"写完觉得对了、提交发现慢了"的细节。

A题：字符串切片的基础考法

题目给出一个由小写英文字母组成的字符串S，以及正整数N。要求去掉S的前N个字符和后N个字符，输出中间剩余部分。约束条件很明确：2N+1 ≤ |S| ≤ 30，N不超过10。

这题考的是对索引边界的敏感度。Python的列表切片S[N:len(S)-N]直接搞定，但新手容易犯的错误是混淆"去掉N个"和"保留到第N个"的区别。代码实现只有三行：

S = list(input())

N = int(input())

print("".join(S[N:len(S)-N]))

注意题目说S长度至少2N+1，意味着中间至少剩1个字符，不会出现空串。这个约束让边界处理变得简单，不需要额外判断。

B题：网格邻接计数的暴力美学

H行W列的网格，要求每个格子输出与其边相邻的格子数量。邻接定义是曼哈顿距离等于1，即上下左右四个方向。

数据范围很小：H和W都不超过50。这意味着全网格最多2500个格子，每个格子检查4个方向，总操作量约1万次，完全不需要优化。

实现思路是双重循环遍历每个坐标(i,j)，再用一个方向数组[(1,0),(0,1),(-1,0),(0,-1)]检查四邻域是否在边界内。代码结构如下：

先初始化一个H×W的零矩阵，然后对每个格子统计有效邻居数，最后按行输出。这里有个细节：输入没有给出网格内容，只给行列数，所以不需要读入字符矩阵，直接根据位置几何判断即可。

容易踩的坑是索引越界检查。Python中0<=i+x<=H-1的写法比单独判断i+x>=0 and i+x

C题：奇数长度子串的中心计数

题目升级：给定长度最多5×10^5的大写字符串S，统计满足两个条件的子串数量——长度为奇数，且正中间的字符是'C'。

关键观察：对于位置i上的'C'，它能作为多少个奇数长度子串的中心？

假设'C'在索引i处（0-based），以它为中心的子串，左边界可以选0到i之间的任意位置，右边界可以选i到len(S)-1之间的任意位置。但要求左右延伸长度相等，即子串形式为S[i-k:i+k+1]，其中k≥0。

因此左半部分可选k+1个位置（0到i共i+1个选择，但受限于右边界），实际最大k受限于min(i, len(S)-1-i)。换句话说，以i为中心的合法子串数量等于min(i+1, len(S)-i)。

实现时只需遍历字符串，遇到'C'就累加min(i+1, len(S)-i)。代码极短：

S = list(input())

count = 0

for i in range(len(S)):

if S[i] == "C":

count += min(i+1, len(S)-i)

print(count)

时间复杂度O(|S|)，对于50万的数据量完全够用。这题的难度在于把"子串计数"转化为"中心位置的几何分析"，而非真的枚举所有子串——后者会超时。

D题：动态中位数维护的核心技巧

400分题，也是本次竞赛的难点。初始黑板上有一个整数X，随后Q个查询，每个查询给出两个整数A_i和B_i，需要先把这两个数写到黑板上，然后输出当前所有数字的中位数。

关键约束：第i次查询后，黑板上有2i+1个数（初始1个，每次加2个），所以中位数就是第i+1小的数。Q最大2×10^5，数值范围10^9，要求每次操作后快速输出中位数。

朴素做法是每次排序，但O(Q^2 log Q)会超时。正确思路是用两个优先队列（堆）维护：

• 小根堆right：存放大于等于中位数的数，堆顶是当前中位数候选

• 大根堆left：存放小于中位数的数，堆顶是left中的最大值

保持不变性：|left| = |right| 或 |left| = |right| + 1。这样中位数就是left的堆顶（取负后的大根堆实现）。

每次加入两个数A和B，需要分情况讨论：

第一步处理A：比较A与left_max（当前中位数）。如果A更小，说明A属于left，但这样left会多一个元素，需要把left_max移到right；反之A直接进right，再从right移一个到left来平衡。

第二步处理B：类似地，比较B与right_min。如果B更大，进right后需要把right_min移到left；反之B进left。

Python中用heapq实现大根堆的技巧是存负数。代码中left存-X，取堆顶时用-heapq.heappop(left)还原。

一个实现细节：为了简化边界处理，初始化时给两个堆都压入正无穷，这样空堆的"堆顶"也有定义，避免每次判断堆是否为空。

最终中位数输出：如果left比right多一个元素，输出left_max；否则按题目逻辑，两个堆大小相等时中位数是left_max（因为总数2i+1是奇数，left始终多一个或相等，但本题每次加两个数，left会严格多一个）。

复盘：哪些写法可以优化

B题的方向数组用元组列表很Pythonic，但也可以用dx=[1,0,-1,0], dy=[0,1,0,-1]配合range(4)循环，性能几乎无差别。

C题的min(i+1, len(S)-i)可以写成min(i, len(S)-1-i)+1，但前者更直观。注意i+1是左半部分可选长度（包含当前字符），len(S)-i是右半部分可选长度（包含当前字符），取最小值就是以i为中心的奇数子串数量。

D题的堆操作比较繁琐，实际比赛中容易写错push/pop的顺序。建议先用纸笔模拟几个例子，确认状态转移正确再编码。一个常见错误是忘记把left_max重新压回left，导致后续查询状态错乱。

四道题整体难度梯度明显：A考语言基础，B考模拟实现，C考观察转化，D考数据结构。对于目标晋升蓝名的选手，C和D的解题思路值得反复琢磨——尤其是"不直接做，而是找性质"的思维模式。