蓝桥杯刷题DAY2：二维前缀和 一维前缀和 差分数组

闪耀的灯光

---

📌 题目描述

蓝桥公园是一个适合夜间散步的好地方，公园可以被视为由 n × m 个矩形区域构成。每个区域都有一盏灯，初始亮度为 a[i][j]。

小蓝可以选择一个大的矩形区域，并按下开关一次，这将使得该区域内每盏灯的亮度减少 1，但每个区域内的灯的亮度最多只能减少至 a[i][j] - c。如果此时亮度已达到 a[i][j] - c，再次按下开关将使得灯的亮度恢复为 a[i][j]。

现在，小蓝将进行 t 次操作。每次操作他会选择一个矩形区域，该区域的左上角端点为 (x₁, y₁)，右下角端点为 (x₂, y₂)，然后将该区域内所有灯按下 k 次开关。

他想知道，在每次操作结束后，该区域内所有灯的总亮度是多少？在下一次操作前，公园内所有灯光会恢复到初始值。

数据保证每盏灯的亮度不会减少至负数。

---

📌 输入格式

• 第一行 输入三个正整数 n、m 和 c，含义如上所述。
• 接下来 n 行，每行输入 m 个正整数，代表灯的初始亮度 a[i][j]。
• 第 n+2 行 输入一个正整数 t，表示小蓝的操作次数。
• 接下来 t 行，每行输入 5 个整数 x₁, y₁, x₂, y₂, k：
  • (x₁, y₁)：矩形区域的左上角坐标。
  • (x₂, y₂)：矩形区域的右下角坐标。
  • k：该区域内所有灯按下的开关次数。

---

📌 输出格式

输出 t 行，每行一个正整数，表示每次操作结束后该区域内所有灯的总亮度。

---

📌 样例输入

3 3 3 14 14 17 13 15 18 13 16 19 3 1 1 2 2 3 2 2 3 3 5 2 3 3 3 4

---

📌 样例输出

44 64 37

---

📌 样例解释

🔹 第一次操作 (1,1) → (2,2), k=3

初始状态

14 14 17 13 15 18 13 16 19

按 3 次开关后

11 11 17 10 12 18 13 16 19

答案：

11 + 11 + 10 + 12 = 44

---

🔹 第二次操作 (2,2) → (3,3), k=5

初始状态

14 14 17 13 15 18 13 16 19

按 5 次开关后

14 14 17 13 14 17 13 15 18

答案：

14 + 17 + 15 + 18 = 64

---

🔹 第三次操作 (2,3) → (3,3), k=4

初始状态

14 14 17 13 15 18 13 16 19

按 4 次开关后

14 14 17 13 15 18 13 16 19

答案：

18 + 19 = 37

---

📌 评测数据规模

约束条件	范围
矩阵大小	1 ≤ n, m ≤ 300
最大减少值	1 ≤ c ≤ 10
操作次数	1 ≤ t ≤ 10⁵
灯的初始亮度	10 ≤ a[i][j] ≤ 10⁹
开关次数	1 ≤ k ≤ 10⁹
查询范围	1 ≤ x₁ ≤ x₂ ≤ n, 1 ≤ y₁ ≤ y₂ ≤ m

---

📌 运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Java	2s	256M
Python3	3s	256M

子串简写

题目描述

程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 internationalization 简写成 i18n，Kubernetes（注意连字符不是字符串的一部分）简写成 K8s，Lanqiao 简写成 L5o 等。

在本题中，我们规定长度 大于等于 K 的字符串都可以采用这种简写方法（长度小于 K 的字符串不配使用这种简写）。

给定一个字符串 S 和两个字符 c1 和 c2，请你计算 S 中 有多少个以 c1 开头，c2 结尾的子串 可以采用这种简写？

---

输入格式

• 第一行包含一个整数 K。
• 第二行包含一个字符串 S 和两个字符 c1 和 c2。

---

输出格式

• 一个整数代表答案。

---

样例输入

4

abababdb a b

样例输出

6

---

样例说明

符合条件的子串如下所示，中括号内是该子串：

---

评测用例规模与约定

• 对于 20% 的数据，保证：2 ≤ K ≤ |S| ≤ 10,000 
• 对于 100% 的数据，保证：2 ≤ K ≤ |S| ≤ 500,000
• S 仅包含小写字母。
• c1 和 c2 均为小写字母。
• |S| 代表字符串 S 的长度。

---

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Java	2s	256M
Python3	3s	256M

题解： 

import os
import sys# 请在此输入您的代码if __name__=="__main__":K=int(input())S,c1,c2=input().split()n=len(S)myarray=[0]*nif S[0]==c2:myarray[0]=1for i in range(1,n):if S[i]==c2:myarray[i]=myarray[i-1]+1else:myarray[i]=myarray[i-1]total=0for i in range(n):if S[i]==c1:l=i+K-1if l<n:total+=myarray[n-1]-myarray[i+K-2]print(total)

重新排序

问题描述

给定一个数组 A 和一些查询 [Li,Ri]，求数组中第 Li 至第 Ri​ 个元素之和。

小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组，所有查询结果的总和最多可以增加多少？

---

输入格式

• 第一行：包含一个整数 n（表示数组 A 的大小）。
• 第二行：包含 n 个整数 A1,A2,…,An​（相邻两个整数之间用空格分隔）。
• 第三行：包含一个整数 m（表示查询的数目）。
• 接下来的 m 行：
  • 每行包含两个整数 Li,Ri​。

---

输出格式

输出一行，包含一个整数，表示所有查询结果的总和相比原数组最多可以增加的值。

---

样例输入

5 1 2 3 4 5 2 1 3 2 5

样例输出

4

样例说明

原数组查询总和：

• 查询 [1,3]：1+2+3=6
• 查询 [2,5]：2+3+4+5=14
• 原总和：6+14=20

重新排列后数组为 (1,4,5,2,3)，查询和变为：

• 查询 [1,3]：1+4+5=10
• 查询 [2,5]：4+5+2+3=14
• 新总和：10+14=24

最大增加值：24−20=4。

---

评测用例规模与约定

评测用例	限制范围
30% 的评测用例	n,m≤50
50% 的评测用例	n,m≤500
70% 的评测用例	n,m≤5000
100% 的评测用例	1≤n,m≤10^5，1≤Ai≤10^6，1≤Li≤Ri≤10^6

---

运行限制

编程语言	最大运行时间	最大运行内存
C++	1s	512M
C	1s	512M
Python3	1s	512M
Java	1s	512M