前缀和and差分习题
最大正方形
题目描述
在一个 $n\times m$ 的只包含 $0$ 和 $1$ 的矩阵里找出一个不包含 $0$ 的最大正方形，输出边长。
输入格式
输入文件第一行为两个整数 $n,m(1\leq n,m\leq 100)$，接下来 $n$ 行，每行 $m$ 个数字，用空格隔开，$0$ 或 $1$。
输出格式
一个整数，最大正方形的边长。
样例 #1
样例输入 #1
1 | 4 4 |
样例输出 #1
1 | 2 |
题解
思路
二维前缀和公式：f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i]j。通过求二维数组的前缀和，当前缀和大于等于要求正方形的边长平方，则输出，否则不输出。二分搜索优化：选择输入边长最小的为边界，然后边长从0开始增加遍历。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using namespace std;
int n, m, ans = 0, x, f[205][205];
int main() {
scanf("%d%d", &n, &m);
for (int i=0; i<n; ++i)
for (int j=0; j<m; ++j) {
scanf("%d", &x);
f[i][j]= f[i-1][j]+f[i][j-1]-f[i-1][j-1]+x;
}
for (int i=0; i<n; ++i)
for (int j=0; j<m; ++j) {
int l = 0, r = min(n,m);
while (l<=r) {
int mid = (l+r)>>1; //二分相当于除以2,就是将l+r的结果往右移一位，相当于二进制/2.
if (i+mid>n || j+mid>m || f[i+mid][j+mid]-f[i+mid][j]-f[i][j+mid]+f[i][j] < mid*mid) r = mid-1;
else l = mid+1;
}
if (f[i+r][j+r]-f[i+r][j]-f[i][j+r]+f[i][j] == r*r) ans = max(ans, r);
}
cout << ans;
return 0;
}
1 |
|
地毯
题目描述
在 $n\times n$ 的格子上有 $m$ 个地毯。
给出这些地毯的信息，问每个点被多少个地毯覆盖。
输入格式
第一行，两个正整数 $n,m$。意义如题所述。
接下来 $m$ 行，每行两个坐标 $(x_1,y_1)$ 和 $(x_2,y_2)$，代表一块地毯，左上角是 $(x_1,y_1)$，右下角是 $(x_2,y_2)$。
输出格式
输出 $n$ 行，每行 $n$ 个正整数。
第 $i$ 行第 $j$ 列的正整数表示 $(i,j)$ 这个格子被多少个地毯覆盖。
样例 #1
样例输入 #1
1 | 5 3 |
样例输出 #1
1 | 0 1 1 1 0 |
提示
样例解释
覆盖第一个地毯后：
| $0$ | $0$ | $0$ | $0$ | $0$ |
|---|---|---|---|---|
| $0$ | $1$ | $1$ | $0$ | $0$ |
| $0$ | $1$ | $1$ | $0$ | $0$ |
| $0$ | $0$ | $0$ | $0$ | $0$ |
| $0$ | $0$ | $0$ | $0$ | $0$ |
覆盖第一、二个地毯后：
| $0$ | $0$ | $0$ | $0$ | $0$ |
|---|---|---|---|---|
| $0$ | $1$ | $1$ | $0$ | $0$ |
| $0$ | $1$ | $2$ | $1$ | $1$ |
| $0$ | $0$ | $1$ | $1$ | $1$ |
| $0$ | $0$ | $1$ | $1$ | $1$ |
覆盖所有地毯后：
| $0$ | $1$ | $1$ | $1$ | $0$ |
|---|---|---|---|---|
| $0$ | $1$ | $1$ | $0$ | $0$ |
| $0$ | $1$ | $2$ | $1$ | $1$ |
| $0$ | $0$ | $1$ | $1$ | $1$ |
| $0$ | $0$ | $1$ | $1$ | $1$ |
数据范围
对于 $20\%$ 的数据，有 $n\le 50$，$m\le 100$。
对于 $100\%$ 的数据，有 $n,m\le 1000$。
题解
思路
这题主要的思路是差分。一维差分公式：d[i]=a[i]-a[i-1]。二维差分公式：d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]。
代码
1 |
|
[HNOI2003] 激光炸弹
题目描述
一种新型的激光炸弹，可以摧毁一个边长为 $m$ 的正方形内的所有目标。现在地图上有 $n$ 个目标，用整数 $x_i$ , $y_i$ 表示目标在地图上的位置，每个目标都有一个价值 $v_i$。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为 $m$ 的边必须与 $x$ 轴，$y$ 轴平行。若目标位于爆破正方形的边上，该目标不会被摧毁。
现在你的任务是计算一颗炸弹最多能炸掉地图上总价值为多少的目标。
可能存在多个目标在同一位置上的情况。
输入格式
输入的第一行为整数 $n$ 和整数 $m$；
接下来的 $n$ 行，每行有 $3$ 个整数 $x, y, v$，表示一个目标的坐标与价值。
输出格式
输出仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过 $32767$ ）。
样例 #1
样例输入 #1
1 | 2 1 |
样例输出 #1
1 | 1 |
提示
数据规模与约定
- 对于 $100\%$ 的数据，保证 $1 \le n \le 10^4$，$0 \le x_i ,y_i \le 5\times 10^3$，$1 \le m \le 5\times 10^3$，$1 \le v_i < 100$。
题解
思路
利用二维前缀和，首先因为炸弹的边上无法炸毁目标，所以需要将目标的横纵坐标+1让它处于炸弹的范围内，避免越界。然后求前缀和。在求区间内目标的价值和。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
using namespace std;
int main(){
int n,m,f[5010][5010];
cin>>n>>m;
int x,y,v;
for(int i=1;i<=n;i++){
cin>>x>>y>>v;
f[x+1][y+1]+=v;
}
int N=5001;
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+f[i][j];
}
}
int ans=0;
for(int i=m;i<=N;i++){
for(int j=m;j<=N;j++){
int num=f[i][j]-f[i-m][j]-f[i][j-m]+f[i-m][j-m];
ans=max(ans,num);
}
}
cout<<ans<<endl;
}
1 |
|
[Poetize6] IncDec Sequence
题目描述
给定一个长度为 $n$ 的数列 ${a_1,a_2,\cdots,a_n}$，每次可以选择一个区间$[l,r]$，使这个区间内的数都加 $1$ 或者都减 $1$。
请问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。
输入格式
第一行一个正整数 $n$
接下来 $n$ 行,每行一个整数,第 $i+1 $行的整数表示 $a_i$。
输出格式
第一行输出最少操作次数
第二行输出最终能得到多少种结果
样例 #1
样例输入 #1
1 | 4 |
样例输出 #1
1 | 1 |
提示
对于 $100\%$ 的数据，$n\le 100000, 0 \le a_i \le 2^{31}$。
题解
思路
首先题目要求经过多少次操作得到数列中的所有数都一样，在输出最少操作数和得到这样的数列有多少种，让数列中所有数都一样就相当于差分数组中除了第一个数以外的其他数都为0，其次我们对正数和负数的操作，正数：a[l,r],b[l]-1,b[r+1]+1;负数：a[l,r],b[l]+1,b[r+1]-1;这两步操作可以归为一步，只要在if语句中判断差分数组中的数是正数还是负数，在用两个变量去存储正数的绝对值的和与负数的绝对值的和。取两者最小的为就让正负数配对，剩下的，再一步步加或减，一步步加或减相当于两者差的绝对值。因此取得的最少操作数为正数的绝对值的和与负数的绝对值的和的最大的那个一个。然后要求这样的数列有多少种，这里我们就是对一步步加或减的操作中，取正数的绝对值的和与负数的绝对值的和的差的绝对值+1。+1是因为差分数组里本身就有一个值，就算不对它进行操作，它也有一种情况。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
using namespace std;
typedef long long LL;
LL n,c,p,q,a[100010];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
for(int i=2;i<=n;i++)
{
c=a[i]-a[i-1];
if(c>0)
{
p+=c;
}
else
q-=c;
}
LL ans1=max(p,q);
LL ans2=abs(p-q)+1;
cout<<ans1<<endl<<ans2;
return 0;
}
1 |
|
[USACO16JAN] Subsequences Summing to Sevens S
题目描述
Farmer John’s $N$ cows are standing in a row, as they have a tendency to do from time to time. Each cow is labeled with a distinct integer ID number so FJ can tell them apart. FJ would like to take a photo of a contiguous group of cows but, due to a traumatic childhood incident involving the numbers $1 \ldots 6$, he only wants to take a picture of a group of cows if their IDs add up to a multiple of 7.
Please help FJ determine the size of the largest group he can photograph.
给你n个数，分别是a[1],a[2],…,a[n]。求一个最长的区间[x,y]，使得区间中的数(a[x],a[x+1],a[x+2],…,a[y-1],a[y])的和能被7整除。输出区间长度。若没有符合要求的区间，输出0。
输入格式
The first line of input contains $N$ ($1 \leq N \leq 50,000$). The next $N$
lines each contain the $N$ integer IDs of the cows (all are in the range
$0 \ldots 1,000,000$).
输出格式
Please output the number of cows in the largest consecutive group whose IDs sum
to a multiple of 7. If no such group exists, output 0.
样例 #1
样例输入 #1
1 | 7 |
样例输出 #1
1 | 5 |
提示
In this example, 5+1+6+2+14 = 28.
题解
思路
这里用到的一个数学定理：若两个数（mod7=0）相减，那么这两个数mod7的余数一定相同。
那么我们只要求出相同的第一个余数和最后一个余数之间的长度就是最长的长度。
因为我们不知道哪两个余数之间是最长，所以枚举7次，从7次中找到最长的。
注意当从后向前求余数的时候，要给首项下标为0的数赋值0。
代码
1 |
|
