Day24 洛谷普及2004（内涵前缀和与差分算法）

零基础洛谷刷题记录

Day01 2024.11.18
Day02 2024.11.25
Day03 2024.11.26
Day04 2024.11.28
Day05 2024.11.29
Day06 2024 12.02
Day07 2024.12.03
Day08 2024 12 05
Day09 2024.12.07
Day10 2024.12.09
Day11 2024.12.10
Day12 2024.12.12
Day13 2024.12.16
Day14 2024.12.17
Day15 2024.12.18
Day16 2024.12.19
Day17 2024.12.21
Day18 2024.12.23
Day19 2024.12.24
Day20 2024.12.25
Day21 2024.12.26
Day22 2025.01.19
Day23 2025.01.21
Day24 2025.02.01

领地选择

2004：题目描述

作为在虚拟世界里统帅千军万马的领袖，小 Z 认为天时、地利、人和三者是缺一不可的，所以，谨慎地选择首都的位置对于小 Z 来说是非常重要的。
首都被认为是一个占地 C×C 的正方形。小 Z 希望你寻找到一个合适的位置，使得首都所占领的位置的土地价值和最高。

2004:AC代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<math.h>

int main()
{
	static int arr[1005][1005];
	int ditu_kuan, ditu_chang, shoudu_bianchang;
	scanf("%d %d %d", &ditu_kuan, &ditu_chang, &shoudu_bianchang);
	for (int i = 1; i <= ditu_kuan; i++)
	{
		for (int j = 1; j <= ditu_chang; j++)
		{
			scanf("%d", &arr[i][j]);
		}
	}
	int shoudu_hang = 0, shoudu_zhong = 0;
	int max = 0;
	for (int i = 1; i <= ditu_chang - shoudu_bianchang + 1;i++)
	{
		for (int j = 1; j <= ditu_kuan - shoudu_bianchang + 1;j++)
		{
			int jiazhi = 0;
			int hang = i;
			while (hang <= i + shoudu_bianchang - 1)
			{
				int lie = j;
				while (lie < j + shoudu_bianchang)
				{
					jiazhi += arr[hang][lie];
					lie++;
				}
				hang++;
			}
			if (jiazhi > max)
			{
				shoudu_hang = i;
				shoudu_zhong = j;
				max = jiazhi;
			}
		}
	}
	printf("%d %d\n", shoudu_hang, shoudu_zhong);
	return 0;
}

2004：学习成果

• 是一道简单的比较题，但是对时间复杂度如何优化呢

一维前缀和

算法：一维前缀和

• 对于数组arr={1,3,7,5,2}，进行q次询问，例如询问【2，4】、【0，3】、【3，4】求和，会有几个数的和进行了重复的计算，时间复杂度是0（nq）
• 前缀和数组的撰写：

> 若 arr={1，3，7，5，2}
> 则 sum{1，1+3=4，7+4=11，11+5=16，16+2=18}
> 其中sum【i】=sum【0】+sum【1】+...+sum【i】=sum【i-1】+arr【i】
> 由此得到arr【i】+arr【i+1】+...+arr【j】=sum【j】-sum【i-1】

一维差分

算法：一维差分

• 对于数组arr={1,3,7,5,2}，进行m次操作，给区间【i，j】中的每个元素都+value，并询问arr的更新结果，复杂度为O（mn）
• 优化思路：由于我们只关心各种操作的结果，而不关心过程（例如对a-5+3+1-2其实就是a-3）
• 引入差分数组

> 对于arr={1，3，7，5，2}
> 差分数组d={1，2，4，-2，-3}
> 观察前缀和数组sum_d={1,3,4,7,2}
> 总结：前缀和是差分的逆运算

• 差分标记

[L,R]+value = d[L]+value,d[R+1]+value//中间都+ value 所以中间差分是不变的，d[R+1]可能不存在
此时时间复杂度变为O(2m+n)

二维前缀和

算法：二维前缀和

• 对于二维矩阵arr【10】【10】，若想计算由arr【2】【2】和arr【5】【5】围成的矩阵元素的和，原始做法就是一个一个累加，时间复杂度为O(mn)
• 优化思路：利用二维前缀和将问题转化为【0，0】到【i，j】的提取算好的简单计算
• 计算公式

sum（【i】【j】到【m】【n】）=sum【m】【n】-sum【i-1】【j】-sum【i】【j-1】+sum【i-1】【j-1】//没写哪到哪，默认（0，0），注意i-1和j-1的越界情况，也可以把下标从1开始避免越界的问题

• 二维前缀和数组的构造

就是利用上面的计算公式即可得到

算法：二维差分

• 对于二维矩阵arr【10】【10】，若想计算由arr【2】【2】和arr【5】【5】围成的矩阵元素都+3，再将由arr【1】【1】和arr【3】【4】围成的矩阵元素都-6，原始做法就是一个一个加，再一个一个减，时间复杂度为O(mn)
• 优化思路：利用差分进行差分标记，将内部的加减转化为差分边界的加减
• 差分标记的影响：将d【i】【j】+1，会导致d【i】【j】的右下角矩阵元素都+1
• 差分标记的公式：

在n×n的矩阵中，将arr【i】【j】到arr【m】【l】的元素都+value，则
d【i】【j】+value
d【i】【l+1】-value
d【m+1】【j】-value
d【m+1】【l+1】+value

2004：代码优化

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<math.h>

int main()
{
	static long long int arr[1005][1005];
	int ditu_kuan, ditu_chang, shoudu_bianchang;
	scanf("%d %d %d", &ditu_kuan, &ditu_chang, &shoudu_bianchang);
	for (int i = 1; i <= ditu_kuan; i++)
	{
		for (int j = 1; j <= ditu_chang; j++)
		{
			scanf("%lld", &arr[i][j]);
		}
	}

	//构建二维前缀和数组
	static long long int sum[1005][1005] = { 0 };
	for (int i = 1; i <= ditu_kuan; i++)
	{
		for (int j = 1; j <= ditu_chang; j++)
		{
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
		}
	}

	int shoudu_hang = 0, shoudu_zhong = 0;
	long long int max = 0;

	for (int i = shoudu_bianchang; i <= ditu_chang; i++)
	{
		for (int j = shoudu_bianchang; j <= ditu_kuan; j++)
		{
			if (sum[i][j] - sum[i][j - shoudu_bianchang] - sum[i - shoudu_bianchang][j] + sum[i - shoudu_bianchang][j - shoudu_bianchang] > max)
			{
				shoudu_hang = i - shoudu_bianchang + 1;
				shoudu_zhong = j - shoudu_bianchang + 1;
				max = sum[i][j] - sum[i][j - shoudu_bianchang] - sum[i - shoudu_bianchang][j] + sum[i - shoudu_bianchang][j - shoudu_bianchang];
			}
		}
	}
	printf("%lld %lld\n", shoudu_hang, shoudu_zhong);
	return 0;
}

• 记得开long long