出题人在此谢罪，题目难度整体偏高，并且G题没有卡掉某些暴力，现在数据已经加强。

题解

A

按照题面模拟

B

当2*A > B时，走到外面再转一圈是更好的，否则就不走外面

C

思维

简单手推一下发现答案只有 -1， 1， 2。

  1. 注意 需特判，因为一个数删不了，所以是 。
  2. 如果 ，答案为 1。
  3. 如果 ，只需要找到一对 ，，，满足 且 ，就可以操作两次删除整个数组。
  4. 其余情况都为 。

时间复杂度 。

D

差分

如果暴力修改的话，此时时间复杂度是 , 会超时。

所以考虑把二维转换成n个一维， 我们只需要把对每个一维的操作通过差分优化，就可以把复杂度降到

然后考虑曼哈顿距离 实际上每次炸弹影响的范围是菱形，我们计算这个菱形在每一行的左右端点，在这上面 进行差分操作

E

动态规划

定义代表的是1到 i 全部删除的最小操作次数。显然答案就是。

+), 当且仅当。

那么现在的问题是对于每个 i 来说如何快速找到 最小的 ,开个桶记录每个值对应最小的 ,然后 转移即可。

时间复杂度 。

F

二维差分

将整个矩阵旋转45度，然后映射到一个 (2 * n) * (2 * n) 新矩形上面，这样原来的菱形操作就可以使用二维差分来维护

举个简单的例子

-1- -2- -3- -4- -5- -6- -7-
-1- (1,4)
-2- (1,3) (2,4)
-3- (1,2) (2,3) (3,4)
-4- (1,1) (2,2) (3,3) (4,4)
-5- (2,1) (3,2) (4,3)
-6- (3,1) (4,2)
-7- (4,1)

对于原来的菱形操作，可以直接在被映射的矩阵维护一个矩形， 假设以（2，3）为中心，半径为1修改操作，就可以直接维护映射后以(2,3)为左上角，(4,5)为右下角的矩形区域

时间复杂度 。

G

线段树 + 字符串哈希

预处理 26 个全是相同字母的哈希数组，然后区间修改只需要打懒标记 O(1) 修改每一段。

判断区间是否是特殊回文串只需要看字符串左边一半的正向哈希值和右边一半的反向哈希值的差值是否为 的形式即可。

具体地，可以类比10进制，假设 X 为 xxxaxx, Y 为 xxxbxx，X 和 Y 只有第三位的数字不同，其它位的数字都相同，那么 X - Y 等于 。

时间复杂度 。