第一部分 知识点讲解

一、数组与下标

1. 一维数组

一维数组可以理解为一排连续的数据：

int a[100005];

如果使用从 $1$ 开始的下标，那么数组中的 $n$ 个数存放在 a[1] 到 a[n] 中。

for(int i=1;i<=n;i++)
{
	cin>>a[i];
}

2. 数组大小

数组大小必须根据题目的数据范围确定，并给边界位置留下空间。

• 若 $n\le 10^5$，可以开 a[100005]。
• 若 $n\le 10^6$，可以开 a[1000005]。
• 差分需要访问 r+1，数组还要能存放第 $n+1$ 个位置。

本周的 P1995 计算能力 前两次只开了 1005 和 10005，而题目中的 $n$ 最大为 $10^5$，因此只能通过部分测试点。

3. 从 $0$ 开始和从 $1$ 开始

做题时可以选择从 $0$ 或从 $1$ 开始，但一段程序中要保持统一。

本周大多数程序使用从 $1$ 开始：

• 第 $i$ 行、第 $j$ 列对应 a[i][j]。
• 前缀和的初始位置是 s[0]=0。
• 区间 $[l,r]$ 的和是 s[r]-s[l-1]。

如果题目要求输出从 $0$ 开始的位置，可以在输出时减 $1$：

cout<<i-1<<" "<<j-1<<endl;

---

二、一维前缀和

1. 前缀和解决什么问题

当题目需要多次查询一个连续区间的信息时，可以先进行一次预处理，再快速回答每次询问。

例如，数组为：

$$a_1,a_2,a_3,\ldots,a_n$$

定义：

$$s_i=a_1+a_2+\cdots+a_i$$

代码为：

s[i]=s[i-1]+a[i];

2. 区间和公式

区间 $[l,r]$ 的和为：

$$a_l+a_{l+1}+\cdots+a_r=s_r-s_{l-1}$$

代码为：

cout<<s[r]-s[l-1]<<endl;

为什么减去 s[l-1]：s[r] 包含第 $1$ 个数到第 $r$ 个数，减去第 $1$ 个数到第 $l-1$ 个数，剩下的正好是第 $l$ 个数到第 $r$ 个数。

3. 前缀和不只能计算“数值之和”

前缀和中保存的内容可以根据题意改变。

例如，查询区间内偶数的个数时：

if(a[i]%2==0)
	s[i]=s[i-1]+1;
else
	s[i]=s[i-1];

此时 s[i] 表示前 $i$ 个数中偶数的个数，区间内偶数的个数仍然是：

s[r]-s[l-1]

同样的方法还可以统计区间内：

• 奇数的个数；
• 正数的个数；
• 大于某个数的元素个数；
• 满足某种条件的元素个数。

关键是先把每个位置转换为 0 或 1：满足条件记为 1，否则记为 0。

4. 固定长度的连续区间

如果要枚举所有长度为 $m$ 的连续区间，可以同时维护左右端点：

for(int l=1,r=m;r<=n;l++,r++)
{
	int sum=s[r]-s[l-1];
}

所有区间依次为：

$$[1,m],[2,m+1],[3,m+2],\ldots,[n-m+1,n]$$

5. 数据类型

如果 $n$ 很大，或者每个 $a_i$ 很大，前缀和可能超过 int 的范围。

例如 P2054 任务的最少完成时间 中，$a_i$ 最大为 $10^{12}$，必须使用 long long：

long long a[1000005],s[1000005];

6. 复杂度

• 建立前缀和：$O(n)$。
• 每次区间查询：$O(1)$。
• $m$ 次查询总复杂度：$O(n+m)$。

---

三、一维差分

1. 差分解决什么问题

前缀和适合“多次查询区间”，差分适合“多次修改区间，最后统一查看结果”。

例如，多次把区间 $[l,r]$ 中的每个数增加 $k$。如果每次都从 $l$ 循环到 $r$，数据较大时会很慢。

2. 差分数组的定义

对于原数组 $a$，定义差分数组 $c$：

$$c_i=a_i-a_{i-1}$$

代码为：

for(int i=1;i<=n;i++)
{
	c[i]=a[i]-a[i-1];
}

3. 区间加法

要把区间 $[l,r]$ 中的每个数增加 $k$，只需要：

c[l]+=k;
c[r+1]-=k;

含义是：

• 从第 $l$ 个位置开始，整体增加 $k$；
• 从第 $r+1$ 个位置开始，取消这次增加。

如果每次只增加 $1$：

c[l]++;
c[r+1]--;

4. 还原原数组

完成所有修改后，对差分数组求一次前缀和：

for(int i=1;i<=n;i++)
{
	a[i]=a[i-1]+c[i];
}

5. 差分完整流程

1. 读入原数组。
2. 建立差分数组。
3. 处理每次区间修改。
4. 对差分数组求前缀和，还原最终数组。
5. 输出答案。

如果原数组一开始全是 $0$，可以省略建立差分数组的步骤，因为全局数组本来就会初始化为 $0$。

6. 本周容易出错的位置

• 忘记输入 l、r、k 就直接修改。
• 把 c[l]+=k 写成 l+=k。
• 忘记修改 c[r+1]。
• 还原时应写 a[i]=a[i-1]+c[i]，不能使用固定的 l。
• 数组必须能访问 r+1。

7. 复杂度

• 建立差分数组：$O(n)$。
• 每次区间修改：$O(1)$。
• 最后还原：$O(n)$。
• 总复杂度：$O(n+q)$。

---

四、二维数组与矩阵

1. 二维数组的含义

int a[105][105];

a[i][j] 表示第 $i$ 行第 $j$ 列的元素。第一个下标是行，第二个下标是列。

2. 输入与遍历

for(int i=1;i<=n;i++)
{
	for(int j=1;j<=m;j++)
	{
		cin>>a[i][j];
	}
}

• 外层循环控制行。
• 内层循环控制列。
• 一个位置只应该处理一次。

3. 直接访问指定位置

要找第 $p$ 行第 $q$ 列，直接使用：

a[p][q]

不需要再用两层循环查找。

本周 P2317 查找数组某位置的数据 的数据范围为 $n\le 3000$，数组不能只开到 60×60。

4. 常见位置条件

对于 $n\times m$ 的矩阵：

位置	条件
第一行	i==1
最后一行	i==n
第一列	j==1
最后一列	j==m
矩阵边缘	`i==1

对于 $n\times n$ 的方阵：

位置	条件
主对角线	i==j
副对角线	i+j==n+1
两条对角线	`i==j

使用 || 可以保证中心元素只处理一次。

5. 判断位置，不是比较元素值

判断矩阵边缘时，应判断行号和列号：

if(i==1||i==n||j==1||j==m)

不能写成：

if(a[i][j]=...)

这里还有一个常见问题：

• = 是赋值；
• == 才是判断是否相等。

6. 矩阵图形与遍历顺序

按行填入时，通常先循环行，再循环列：

for(int i=1;i<=n;i++)
{
	for(int j=1;j<=n;j++)
	{
		cnt++;
		a[i][j]=cnt;
	}
}

按列填入时，可以交换循环的先后顺序：

for(int j=1;j<=n;j++)
{
	for(int i=1;i<=n;i++)
	{
		cnt++;
		a[i][j]=cnt;
	}
}

输出图形时要确认输出的是 a[i][j]，而不是一直输出最终的 cnt。

7. 场宽输出

题目要求每个数字占固定宽度时，可以使用 setw：

cout<<setw(3)<<a[i][j];

setw(3) 只对紧接着输出的一个数据生效，因此每次输出元素时都要写。

---

五、字符与 ASCII

1. 字符常量

单个字符使用单引号：

char c='A';

字符串使用双引号：

cout<<"YES";

2. 判断字符类别

if(c>='a'&&c<='z')  // 小写字母
if(c>='A'&&c<='Z')  // 大写字母
if(c>='0'&&c<='9')  // 数字字符

注意：字符 '8' 和整数 8 不相同。

3. 字符可以进行加减

英文字母和数字字符在 ASCII 表中是连续排列的，因此：

c+1

可以得到当前字符的后一个字符，但遇到 z、Z 等边界时需要单独处理。

建议使用字符之间的相对位置进行大小写转换，不要死记 31、33、57 等数字：

char upper=c-'a'+'A';
char lower=c-'A'+'a';

这样更容易看懂，也不容易算错。

4. 扫描若干字符

for(int i=1;i<=n;i++)
{
	cin>>c;
}

如果要判断是否出现过字符 '8'：

• 找到 '8' 后可以立即输出 YES 并结束程序；
• 只有检查完全部字符都没有找到，才能输出 NO；
• 不能在第一次遇到非 '8' 的字符时就输出 NO。

5. 使用结束标志

如果输入以 # 结束：

while(cin>>c)
{
	if(c=='#')
		break;
	// 处理 c
}

6. if 与 else if

当多个情况互不重叠、只应该执行一个分支时，使用 if...else if...else。

if(c>='a'&&c<='z')
{
	// 小写字母
}
else if(c>='A'&&c<='Z')
{
	// 大写字母
}

本周 P3425 下一个字母Ⅱ 的第二次提交得到 $50$ 分，原因是修改小写字母之后，又被后面的独立 if 当作大写字母处理了一次。改为 else if 后，每个字符只进入一个分支。

---

六、输入输出与程序细节

1. 严格按照题目格式输出

评测系统会比较输出内容。空格、换行、大小写和标点都可能影响结果。

例如 B0346 分果汁 要求输出两行：

125.000
8

不能输出在同一行：

125.000 8

2. 保留小数

printf("%.2lf",x);  // 保留两位小数
printf("%.3lf",x);  // 保留三位小数

%lf 对应 double。如果参与除法的两个数都是整数，要先转换成实数：

printf("%.2lf",1.0*sum/m);

3. 编译错误与答案错误

• CE：程序不能通过编译，常见原因是变量未定义、单词拼错、引号或括号缺失。
• WA：程序可以运行，但答案不正确，常见原因是公式、边界、下标或输出格式错误。
• 部分分：通常说明主要思路接近正确，但数组范围、数据类型或特殊情况没有处理完整。

4. 提交前检查清单

1. 数组大小是否覆盖题目最大范围？
2. int 是否可能溢出，是否需要 long long？
3. 循环是 <n 还是 <=n？
4. 行、列下标是否写反？
5. = 和 == 是否使用正确？
6. 区间公式是否写成 s[r]-s[l-1]？
7. 差分是否修改了 c[l] 和 c[r+1]？
8. 输出的空格、换行、小数位数和大小写是否完全符合题目？

第二部分 代表例题与代码

例题一 P1995 计算能力：区间和

题意

给定 $n$ 个数和 $m$ 次询问，每次求区间 $[x,y]$ 中所有数的和。

核心

先建立数值前缀和，再用 s[y]-s[x-1] 回答询问。由于 $n,m\le 10^5$，数组至少要开到 100005。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],s[100005],x,y;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	while(m--)
	{
		cin>>x>>y;
		cout<<s[y]-s[x-1]<<'\n';
	}
	return 0;
}

例题二 P5386 偶数个数：条件计数前缀和

题意

多次询问区间 $[l,r]$ 内有多少个偶数。

核心

读入 a[i] 后，判断的是 a[i] 是否为偶数。s[i] 表示前 $i$ 个数中偶数的个数。

#include<bits/stdc++.h>
using namespace std;
int n,q,a[1000005],s[1000005],l,r;
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		s[i]=s[i-1];
		if(a[i]%2==0)
			s[i]++;
	}
	while(q--)
	{
		cin>>l>>r;
		cout<<s[r]-s[l-1]<<'\n';
	}
	return 0;
}

例题三 P1997 倒水：区间增加

题意

有 $n$ 个杯子，进行 $k$ 次操作。每次把第 $l$ 个到第 $r$ 个杯子的水量都增加 $p$，求最终水量。

核心

对原数组建立差分。每次操作只修改 c[l] 和 c[r+1]，最后统一还原。

#include<bits/stdc++.h>
using namespace std;
int n,k,a[200005],c[200005],l,r,p;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		c[i]=a[i]-a[i-1];
	}
	while(k--)
	{
		cin>>l>>r>>p;
		c[l]+=p;
		c[r+1]-=p;
	}
	for(int i=1;i<=n;i++)
	{
		a[i]=a[i-1]+c[i];
		cout<<a[i]<<" ";
	}
	return 0;
}

例题四 P2354 两条对角线之和：位置判断

题意

求方阵两条对角线上的元素之和，中心位置不能重复计算。

核心

主对角线满足 i==j，副对角线满足 i+j==n+1。使用 ||，一个位置最多加一次。

#include<bits/stdc++.h>
using namespace std;
int n,a[10][10],sum;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
			if(i==j||i+j==n+1)
				sum+=a[i][j];
		}
	}
	cout<<sum;
	return 0;
}

例题五 P2702 计算矩阵边缘元素之和

题意

求矩阵第一行、最后一行、第一列和最后一列中所有元素的和。

核心

判断的是位置 (i,j) 是否位于边缘，而不是当前元素的数值。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[105][105],sum;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			if(i==1||i==n||j==1||j==m)
				sum+=a[i][j];
		}
	}
	cout<<sum;
	return 0;
}

例题六 P1184 数字走向 I：按行生成矩阵

题意

输出一个 $n\times n$ 的方阵，数字从 $1$ 开始按行递增，每个数字的场宽为 $3$。

核心

外层循环枚举行，内层循环枚举列。每经过一个位置，计数器增加 $1$。

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	cin>>n;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cnt++;
			cout<<setw(3)<<cnt;
		}
		cout<<endl;
	}
	return 0;
}

例题七 P3425 下一个字母Ⅱ：字符变换

题意

把输入字母变成字母表中的后一个字母，同时交换大小写。z 变为 A，Z 变为 a。

核心

先判断原字符是小写还是大写，每个字符只能进入一个分支。边界 z 和 Z 单独处理。

#include<bits/stdc++.h>
using namespace std;
char c;
int main(){
	cin>>c;
	if(c>='a'&&c<='z')
	{
		if(c=='z')
			c='A';
		else
			c=c-'a'+'A'+1;
	}
	else if(c>='A'&&c<='Z')
	{
		if(c=='Z')
			c='a';
		else
			c=c-'A'+'a'+1;
	}
	cout<<c;
	return 0;
}

例题八 P1097 统计字符的个数

题意

不断读入字符，遇到 # 结束，统计大写字母、小写字母和数字字符的个数。

核心

每读入一个字符先判断是否结束，再根据字符范围分类计数。

#include<bits/stdc++.h>
using namespace std;
char c;
int upper,lower,digit;
int main(){
	while(cin>>c)
	{
		if(c=='#')
			break;
		if(c>='A'&&c<='Z')
			upper++;
		else if(c>='a'&&c<='z')
			lower++;
		else if(c>='0'&&c<='9')
			digit++;
	}
	cout<<upper<<" "<<lower<<" "<<digit;
	return 0;
}

例题九 B0346 分果汁：输出格式

题意

把 $t$ 毫升果汁平均分给 $n$ 名同学，输出每人分到的果汁量和需要的杯子数量。每名同学需要两个杯子。

本周错误

计算方法正确，但题目要求两个答案分别占一行，提交代码却在两个答案之间输出了空格，因此得到 WA。

正确代码

#include<bits/stdc++.h>
using namespace std;
double t;
int n;
int main(){
	cin>>t>>n;
	printf("%.3lf\n",t/n);
	cout<<n*2<<endl;
	return 0;
}

第三部分 本周复习建议

已掌握

• 能使用前缀和完成区间求和和区间计数。
• 能使用差分完成区间增加并还原数组。
• 能使用两层循环完成矩阵输入、统计和图形输出。
• 能判断主对角线、副对角线和矩阵边缘。
• 能判断大小写字母、数字字符，并进行基本字符变换。

需要重点巩固

1. 先看数据范围再开数组。 本周多次因为数组过小只能得到部分分或 WA。
2. 区分“数据”和“位置”。 例如判断偶数要看 a[i]，判断矩阵边缘要看 i、j。
3. 差分的两端必须成对修改。 c[l]+=k 与 c[r+1]-=k 缺一不可。
4. 行列下标不能写反。 a[i][j] 中先行后列。
5. 互斥条件使用 else if。 防止一个字符被连续处理两次。
6. 最后再输出否定答案。 查找字符时，遍历完仍未找到才能输出 NO。
7. 逐字核对输出格式。 特别注意换行、空格、大小写和小数位数。

建议复习顺序

1. 重新口述前缀和公式和差分公式，不看代码写出模板。
2. 重做 P5386 偶数个数，确认理解“条件计数前缀和”。
3. 重做 P5379 差分_模板，完整写出建立、修改、还原三步。
4. 重做 P1186 数字走向III，重点检查行列和输出元素。
5. 重做 P2317 查找数组某位置的数据，先检查数据范围再定义数组。
6. 重做 P3429 字符'8'I，理解为什么 NO 必须在循环结束后输出。
7. 补做并通过 B0346 分果汁，养成提交前核对输出格式的习惯。