AcWing 算法基础课week 1 总结(万字长文)

AcWing 算法基础课week 1 总结

总结点 1:快速排序(分治思想)

题1:从小到大排序

主体思路:定义一个数x属于数组s,利用双指针,将数组分为大于等于x和小于等于x的两部分,然后递归处理。(具体步骤如下)

1.

如上图所示,我们定义一个数组s用来储存n个数据,然后定义两个指针i j,分别指向数组的左右两端,同时i指针逐个向右移动扫描数组,j指针同理向左。

2.

当i,j指针扫描的过程中,当s[i]>x时,指针i就停止移动,同理当s[j]<x时,指针j就停止移动,然后交换s[i]与s[j],那么就使得大于x的s[i]去到了右边的数组,小于x的s[j]去到了左边的数组。

while(i<j)
{
    do i++;while(s[i]<x);//i指针向右移动,当s[i]>x,移动停止,j同理
    do j--;while(s[j]>x);
    if(i<j)swap(s[i],s[j]);//如果i<j说明s[j]<x<s[i],就进行交换
}

3.

重复以上操作,直到i>=j为止。然后相同的方式利用递归处理左右两半边的数组,直到子数组长度等于1。

quick_sort(s,l,j);
quick_sort(s,j+1;r);

完整代码如下

int n;
int s[1000010];
void quick_sort(int s[], int l, int r)//将s[]数组的l-r区间内的数据排序
{
	if (l >= r)return;
    //以中点数据值作为分界值,避免边界问题。
    //注意:以s[l],s[r]作为分界值时需要考虑边界问题,所以直接取中点値
	int x = s[l + r >> 1], i = l - 1, j = r + 1;
	while (i < j)
	{
		do i++; while (s[i] < x);//指针移动直到遇到不符合条件的值
		do j--; while (s[j] > x);
		if (i < j)swap(s[i], s[j]);//交换两值
	}
	quick_sort(s, l, j);//递归处理左右两边
	quick_sort(s, j + 1, r);
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> s[i];
	}
	quick_sort(s, 0, n - 1);//将s[]数组的l-r区间内的数据排序
	for (int i = 0; i < n; i++)
	{
		cout << s[i] << ' ';
	}
	return 0;
}

题2:找到第k小的数(快速排序的拓展)

主体思路与快排相同,只是递归方式不同。

扫描方式与快排相同,我们直接说不同点(递归);

当我们利用双指针i,j扫描一个区间时,肯定会将一个区间分成两部分,而我们需要找到第k个数,这个数可能在前半部分或者后半部分,所以我们分情况递归。

1.如果k在前一部分,就只递归前一部分

2.如果在后一部分,就递归后面

int sl = j-l+1;//sl记录的是前一部分有多少个数
if(k<=sl) return quick_sort(s,l,j,k);
else return quick_sort(s,j+1,r,k-(j-l+1));
//注意我们这里输入的第四个变量是指所求数在某一区间的相对位置。
//如果在右边,因为左边部分已经有j-l+1个数了,所以我们应该找这一区间的第k-(j-l+1)个数

完整代码:

int n, k;
vector<int> s;
int quick_sort(vector<int> s, int l, int r, int k)
{
	if (l >= r)return s[l];//如果区间长度为1,返回0
	int i = l - 1, j = r + 1, x = s[l + r >> 1];
	while (i < j)
	{
		do i++; while (s[i] < x);
		do j--; while (s[j] > x);
		if (i < j)swap(s[i], s[j]);
	}
	int sl = j - l + 1;//计算左边部分有多少个数
	if (k <= sl)return quick_sort(s, l, j, k);//递归左边
	else return quick_sort(s, j + 1, r, k - (j - l + 1));//递归右边
}
int main()
{
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		s.push_back(x);
	}
	cout << quick_sort(s, 0, n - 1, k) << endl;
	return 0;
}

总结点2:归并排序(分治思想)

题1:排序

主体思路:将数组均分为两半部分,分别有序化,然后合并两个数组

1.

将数组均分为两半部分,利用递归分别有序化。

int mid = l+r>>1;
merge_sort(s,l,mid);
merge_sort(s,mid+1,r);

2.

合并两个数组。利用两个指针i,j分别指向两个数组的起始位置,如果s[i]<s[j]就将s[i]放入新数组,反之放入s[j]。

int temp[1000010];//新数组
int k = 0,i = l,j = mid+1;//k负责控制新数组的下标
while(i<=mid&&j<=r)
{
	if(s[i]<s[j]) temp[k++] = s[i++];
	else temp[k++] = s[j++];
}

3.

因为我们上面使用的循环条件时while(i<=mid&&j<=r),所以当一个数组中的全部元素全部放入新数组时,另一个数组可能会还有剩余的数据,所以我们需要将这些数据也放入新数组中。

while(i<=mid) temp[k++] = s[i++];
while(l<=r) temp[k++] = s[j++];

4.

最后需要将新数组中的数据储存回原数组中,因为递归的过程中需要再次用到原数组,所以必须储存回去。

for(int i = l,j = 0;i<=r;i++,j++) s[i] = temp[j];//i控制原数组,j控制临时数组

完整代码如下:

int n;
int s[1000010];
void a(int s[], int l, int r)
{
	if (l >= r)return;
	int temp[1000010];
	int mid = l + r >> 1;
	a(s, l, mid);
	a(s, mid + 1, r);
	int k = 0, i = l, j = mid + 1;
	while (i <= mid && j <= r)
	{
		if (s[i] < s[j])temp[k++] = s[i++];
		else temp[k++] = s[j++];
	}
	while (i <= mid) temp[k++] = s[i++];
	while (j <= r)temp[k++] = s[j++];
	for (int i = l, j = 0; i <= r; i++, j++)
	{
		s[i] = temp[j];
	}
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)cin >> s[i];
	a(s, 0, n - 1);
	for (int i = 0; i < n; i++)cout << s[i] << ' ';
	return 0;
}

题2:逆序对的数量

主体思想:利用归并排序的将两个数组分别有序化后合并的特点,递归计算逆序对的数量

1.

因为思路同归并排序,我们直接讲不同点。

对于一组逆序对,可以分为图中的三种情况:

1.同时在左侧数组

2.同时在右侧数组

3.分别在左右两侧数组

发现对于1,2种情况,当我们将数组进行递归排序时,总有一个区间可以使得两个数分别在数组中点的左右两侧,从而转化为第3种情况,所以我们只考虑第三种情况。

2.

考虑图中的情况,因为两个数组都已经有序化,所以对于s[j]发现有s[i]到s[mid]的部分(图中红色部分)都大于s[j],所以后面的所有数都可与s[j]构成第三种逆序对,逆序对的数量为mid-i+1。

3.

完整代码实现:

const int N = 100010;
int n;
int a[N];
long long ans;
long long merge_sort(int l, int r)
{
	if (l >= r)return 0;
	int mid = l + r >> 1;//中点
	merge_sort(l, mid);//递归处理左右两边,是左右两边有序化
	merge_sort(mid + 1, r);
	int temp[N];//临时数组
	int i = l, j = mid + 1, k = 0;
	while (i <= mid && j <= r)
	{
		if (a[i] <= a[j])temp[k++] = a[i++];//将小的数放入临时数组
		else
		{
			temp[k++] = a[j++];
            //如果s[i]>s[j],说明s[i]-s[mid]的数都与s[j]构成逆序对
            //个数为mid-i+1
			ans += mid - i + 1;
		}
	}
	while (i <= mid) temp[k++] = a[i++];
	while (j <= r)temp[k++] = a[j++];
	for (int i = l, j = 0; i <= r; i++, j++)a[i] = temp[j];
	return ans;
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	cout << merge_sort(0, n - 1) << endl;
	return 0;
}

总结点3:二分

直接讲整数二分,浮点数二分只需要修改细节就好,后面会讲

1.

每次找到区间的中点,将s[mid]与x的值相比较。如果是图中的这种情况,x>s[mid] ,所以x存在于右区间。那么调整区间,将区间的左端点调整为mid+1(为什么是mid+1后面会讲),再去循环处理右区间。另一种情况同理。

2.

因为存在边界问题,所以这里的二分需要分情况讨论,对应的代码也有两种。

首先是边界调整的问题。重要的就是那边可以取到最后的值x,就将哪边的边界调整为mid。直接看代码讲。(代码题目是找到x在数组中的位置)

先看第一种

int l = 0,r = n-1//设置左右端点
while(l<r)
{
	int mid = l+r>>1;//设置中点
	if(s[mid]<=x) r = mid;
    //注意此时x可以在这个判断条件中取到,所以这个条件对应的边界调整为mid
	else l = mid+1;
    //另一个对应的调整为mid+1或mid-1;
}

再看第二种

int l = 0,r = n-1;
while(l<r)
{
	int mid = l+r+1>>1;
	if(s[mid]<=x) l = mid;
    //这时x可以在新的条件中取到,所以对应边界调整为mid,其余同理。
	else r = mid-1;
}

3.

另外的,两种情况所移动的方向不同。

当用第一种模版时,将会从数组左向右去找x的值,直到从左向右找到第一个数为止,此时的边界l就是第一个x的位置。

当用第二种模版时,将会从右向左,直到找到一个数为止,l代表找到的第一个x的位置,注意使用这个模版时,mid = l+r+1>>1。

我们下面看例题

题1:找到一个数的范围

主体思路:利用第一种模版找到左边界,然后利用第二种去找右边界

看代码:

int main()
{
	int n, q;//n是数组长度,注意默认是升序排列,然后q个查询
	cin >> n >> q;
	vector<int> s(n);
	for (auto& n : s)
	{
		cin >> n;
	}
	while (q--)
	{
		int x;
		cin >> x;
		int l = 0, r = n - 1;//设置左右边界
		while (l < r)//找到左边界
		{
			int mid = l + r >> 1;
			if (s[mid] >= x)r = mid;
			else l = mid + 1;
		}
		if (s[l] != x)//如果没有X就输出-1 -1
		{
			cout << "-1 -1" << endl;
		}
		else
		{
			cout << l << ' ';
			l = 0; r = n - 1;
			while (l < r)//找到右边界
			{
				int mid = l + r +1>> 1;//注意+1的细节
				if (s[mid] <= x)l = mid;
				else r = mid - 1;
			}
			cout << l << endl;
		}
	}
	return 0;
}

题2:数的三次方根

这个题就是浮点数二分,浮点数二分比整数二分简单,因为没有边界条件,两个值都去调整为mid。

不多说,直接看代码:

double n;
bool check(double x)//利用check函数去判断条件
{
	return x * x * x < n;
}
int main()
{
	cin >> n;
	double l = -10000, r = 10000;//题目中给的左右边界的范围
	while (fabs(r - l) > 1e-8)//浮点数相等的判断
	{
		double mid = (l + r) / 2;
		if (check(mid)) l = mid;//两个都去调整为mid
		else r = mid;
	}
	cout << fixed << setprecision(6) << l;//输出6位小数
	return 0;
}

总结点4:高精度

所有的高精度都是利用数组去储存一个数,然后通过模拟手算的方式去计算。(之前有发过一期高精度,但是看了y神的代码之后,决定去学习一下y神的代码,很美观)

1.高精度加法

高精加的主体思路就是将两个数组的相同位置上的数字相加,如果大于10就进位。

核心代码看一下:

vector<int > c;
int t= 0;
for(int i = 0;i<max(a.size(),b.size());i++)
{
    if(i<a.size()) t+=a[i];
    if(i<b.size()) t+=b[i];
    c.push_back(t%10);
    t/=10;
}
if(t) c.push_back(t);
return c;

完整代码如下:

string x, y;
vector<int> add(vector<int > a, vector<int> b)
{
	vector<int>  c;
	int t = 0;
	for (int i = 0; i < max(a.size(), b.size()); i++)
	{
		if (i < a.size())t += a[i];//如果a有这位数字,就加上
		if (i < b.size())t += b[i];
		c.push_back(t % 10);//每次将t的个位数输入到c中
		t /= 10;//保留t的10位进行下一次计算
	}
	if (t)c.push_back(t);//因为加法可能有进位,所以最后检查一下进位
	return c;
}
int main()
{
	cin >> x >> y;
	vector<int> a, b;
    //两个字符串倒序输入到数组中
	for (int i = x.size() - 1; i >= 0; i--)a.push_back(x[i] - '0');
	for (int i = y.size() - 1; i >= 0; i--)b.push_back(y[i] - '0');
	auto c = add(a, b);
    //倒序输出
	for (int i = c.size() - 1; i >= 0; i--)cout << c[i];
	return 0;
}

2.高精度减法

1.两个数相减,如果小于0,就进位。

vector<int> c;
int t = 0;
for (int i = 0,t = 0; i < a.size(); i++)
{
	t = a[i] - t;//t储存的是上一位的借位,先减去。
	if (i < b.size())t -= b[i];//如果b存在这位数,就减去
	c.push_back((t + 10) % 10);
    //减去之后,t有可能是负数需要借位,所以利用(t+10)%10,输出借位后的结果
	if (t < 0) t = 1;//如果t<10,就借位
	else t = 0;
}
while (c.size() > 1 && c.back() == 0)c.pop_back();//除前导0
return c;

2.那么到这里就有问题了,上面的代码我们只考虑了A>B的情况,那么A-B<0时怎么办?

很简单,只要用B-A,然后提起输出一个负号就好啦。

那我们先判断A是否大于B;

bool check(vector<int> a,vector<int> b)
{
    //如果位数不一样,位数多的大
    if(a.size()!=b.size()) return a.size()>b.size();
    //如果位数一样,就从高位到低位逐位判断
    //因为我们倒序将字符串转化为了数组,所以高位在最后面
    for(int i = a,size()-1;i>=0;i--)
    {
		if(a[i]!=b[i]) return a[i]>b[i];
    }
}

下面是完整代码:

string x, y;
bool cmp(vector<int> a, vector<int> b)//判断大小
{
	if (a.size() != b.size())return a.size() > b.size();
	for (int i = a.size() - 1; i >= 0; i--)
	{
		if (a[i] != b[i])return a[i] > b[i];
	}
	return true;
}
vector<int> sub(vector<int> a, vector<int> b)
{
	vector<int> c;
	for (int i = 0,t = 0; i < a.size(); i++)
	{
		t = a[i] - t;
		if (i < b.size())t -= b[i];
		c.push_back((t + 10) % 10);
		if (t < 0) t = 1;
		else t = 0;
	}
	while (c.size() > 1 && c.back() == 0)c.pop_back();
	return c;
}
int main()
{
	cin >> x >> y;
	vector<int > a, b;
	for (int i = x.size() - 1; i >= 0; i--)a.push_back(x[i] - '0');
	for (int i = y.size() - 1; i >= 0; i--)b.push_back(y[i] - '0');
	if (cmp(a, b))//如果a>b,正常计算
	{
		auto c = sub(a,b);
		for (int i = c.size() - 1; i >= 0; i--)cout << c[i];
	}
	else//如果b>a
	{
		auto c = sub(b, a);
		cout << '-';//先输出’-‘
        //然后输出b-a
		for (int i = c.size() - 1; i >= 0; i--)cout << c[i];
	}
}

3.高精度乘法(大数乘小数)

如图示(利用的就是乘法与c[i]的规律,具体证明省略,如想看,请评论区提问),直接就得到核心代码:

vector<int> mul(vector<int> a, int b)
{
	vector<int> c;
    //注意循环条件
	for (int i = 0, t = 0; i < a.size() || t; i++)//注意乘法时,当a被执行完后,t不一定为0,但还需要继续将t输入到c中
	{
		if (i < a.size())t += a[i] * b;//如果a有这位数,就t+=a[i]*b;
		c.push_back(t % 10);//将t的个位输入到c中
		t /= 10;
	}
	while (c.size() > 1 && c.back() == 0)c.pop_back();//去除前导0
	return c;
}

完整代码如下:

string x;
int b;
vector<int> mul(vector<int> a, int b)
{
	vector<int> c;
	for (int i = 0, t = 0; i < a.size() || t; i++)
	{
		if (i < a.size())t += a[i] * b;
		c.push_back(t % 10);
		t /= 10;
	}
	while (c.size() > 1 && c.back() == 0)c.pop_back();
	return c;
}
int main()
{
	cin >> x >> b;
	vector<int> a;
	for (int i = x.size() - 1; i >= 0; i--)a.push_back(x[i] - '0');
	auto c = mul(a, b);
	for (int i = c.size() - 1; i >= 0; i--)cout << c[i];
	return 0;
}

4.高精度除法

如图,我们设定b数组为被除数,a为除数,r为余数。

我们从b高位到低位进行计算,那么第一个商c0就应该等于b[4]/a的商,然后余数r就等于b[4]%a;

下一次的除数就等于r*10+b[i],反复计算。

下面看代码实现:(因为我们要保证加减乘除的输入方式统一,所以在输入a数组时依旧是倒序输入)

//代码中的a与b与图中的a,b相反。

vector<int> div(vector<int> &a, int &b,int &r)
{
	vector<int> c;
	for (int i = a.size() - 1; i >= 0; i--)//因为a是倒序输入,但是除法需要从高位到低位进行计算,所以i = a.size()-1
	{
		r = r * 10 + a[i];//每一次的被除数等于r*10+a[i]
		c.push_back(r / b);//商等于r/b;
		r %= b;余数等于r%b
	}
	reverse(c.begin(), c.end());//反转之后消除前导0
	while (c.size() > 1 && c.back() == 0)c.pop_back();
	return c;
}

完整代码如下:

vector<int> div(vector<int> &a, int &b,int &r)
{
	vector<int> c;
	for (int i = a.size() - 1; i >= 0; i--)
	{
		r = r * 10 + a[i];
		c.push_back(r / b);
		r %= b;
	}
	reverse(c.begin(), c.end());
	while (c.size() > 1 && c.back() == 0)c.pop_back();
	return c;
}

int main()
{
	string x;
	int b;
	cin >> x >> b;
	vector<int> a;
	for (int i = x.size() - 1; i >= 0; i--)a.push_back(x[i] - '0');
	int r = 0;
	auto c = div(a, b,r);
	for (int i = c.size() - 1; i >= 0; i--)
	{
		cout << c[i];
	}
	cout << endl << r << endl;
	return 0;
}

总结点5:前缀和与差分

前缀和与差分互为逆运算。

1.前缀和

首先我们先介绍前缀和。先去定义一个数组a,储存n个数据,然后定义一个数组b,去储存前缀和。

那么b[0] = a[0],b[1] = a[0] + a[1],b[2] = a[0] + a[1] + a[2],.......;

以上的b数组就是a的前缀和数组,

前缀和就是将前k个数相加,这个和就是前缀和。

然后我们根据b数组的特点,可以得出以下的递推公式:

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

有了这个特点之后,我们就可以递推计算出b数组的全部初始值,代码如下:

	vector<int> s(n + 1);
	s[0] = 0;//注意两个数组的边界问题
	for (int i = 1; i < n + 1; i++)
	{
		cin >> s[i];
	}
	vector<int> a;
	a.push_back(0);//由于递推公式中有a[i-1],所以我们的循环从i = 1开始,以避免边界问题,对应的s也从i= 1开始储存。
	for (int i = 1; i <= n; i++)
	{
		a.push_back(a[i - 1] + s[i]);
	}

那么我们有了初始化之后的前缀和数组之后,就可以很快的计算出一个区间内所有元素的和,

我们输入所求期间的左边界l,和右边界r,那么这一段区间的和就可以表示为,b[r]-b[l-1];

完整代码实现如下:

int main()
{
	int n, m;//数组长度为n,询问个数为m
	cin >> n >> m;
	vector<int> s(n + 1);
	s[0] = 0;
	for (int i = 1; i < n + 1; i++)
	{
		cin >> s[i];
	}
	vector<int> a;
	a.push_back(0);
	for (int i = 1; i <= n; i++)
	{
		a.push_back(a[i - 1] + s[i]);
	}
	while (m--)//m个询问
	{
		int l, r;
		cin >> l >> r;
		cout << a[r] - a[l - 1] << endl;
	}
	return 0;
}

2.差分

那么前缀和和差分是分不开的,所以我们下面去介绍差分。

差分和前缀和是互为逆运算,那么我们先给出一个前缀和数组a,然后定义一个原数组b;

所以这个a叫做b的前缀和,b叫做a的差分。

那么我们根据两者的关系,就可以根据前缀和数组求出原数组,然而我们其实并不需要掌握求原数组的方法,重要的是掌握它的性质。

我们去看一个例题:

1.首先我们将a,b,数组的全部元素全部初始化为0,

2.我们要进行的操作是在l-r之间的每个数+c,其实我们初始时输入的数组可以看成在i-i之间插入元素a[i],所以将两种操作合并为一种。

下面是重点思路:我们将要进行操作的数组看做前缀和数组a,然后假想一个原数组b。

要想在l-r之间的每个数+c,可以将原数组中的b[l]+=c;

那么在a[l]之后所有的a[]将都加上一个c,(因为图中红色部分和绿色部分所有的a[]都含有b[l]这一项);

但我们最终是要在l-r之间的数+c,所以需要打一个补丁(即将a[r+1]-=c,只有绿色部分含有a[r+1],而红色部分不含有),那么这样就使得a[r]之后的所有a[]回归正常。

总结以上的思路,可以得出核心代码:

void insert(int l, int r, int x)
{
	a[l] += x;
	a[r + 1] -= x;
}

完整代码如下:

const int N = 100010;
int a[N];
void insert(int l, int r, int x)//插入函数
{
	a[l] += x;
	a[r + 1] -= x;
}
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		insert(i, i, x);//初始化数组可以看做在i-i之间插入x
	}
	while (m--)//m组操作
	{
		int l, r, c;
		cin >> l >> r >> c;
		insert(l, r, c);
	}
 
	for (int i = 1; i <= n; i++)//利用差分求出前缀和数组
	{
		a[i] += a[i - 1];
	}
	for (int i = 1; i <= n; i++)
	{
		cout << a[i] << ' ';
	}
	return 0;
}

3.二维前缀和

那么有了以上的基础,我们将前缀和拓展到2维,求一下二维前缀和;

同样的道理,我们定义两个二维数组a,b,a为前缀和数组,b为原数组;

我们要计算前缀和a[i,j];可以看出a[i,j]由两个红色部分,一个绿色部分和一个棕色部分组成。

那可以得出表达式:a[i,j] = a[i-1,j]->(一个绿色+一个红色)+a[i,j-1]->(一个绿色+一个红色)+b[i,j]->(棕色部分)-a[i-1,j-1]->(减去多余的绿色部分)

由此得出核心代码:

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

那么我们得到一个已经初始化的前缀和数组,就可以求出图形中任意一个矩阵中的元素和;

例如上图,我们要求白色矩阵中所有的元素和,可以用金色边框内所有的元素减去绿色部分,再减去蓝色部分,最后将两部分重叠的部分加回来,就得到了所求。

代码如下:

cout << b[x2][y2] - b[x1 - 1][y2] - b[x2][y1 - 1] + b[x1 - 1][y1 - 1]<<endl;

完整代码:

const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
int main()
{
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> a[i][j];
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];
		}
	}
	while (q--)
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		cout << b[x2][y2] - b[x1 - 1][y2] - b[x2][y1 - 1] + b[x1 - 1][y1 - 1]<<endl;
	}
	return 0;
}

3.二维差分

同样的不需要掌握如何求差分,只需要掌握它的性质。

直接看一道题

将数组(x2,y2),(x1,y1)构成的矩阵中的所有元素+c

我们还是将要操作的数组看做前缀和数组a,假想一个原数组b。

当我们给b[i,j]+c之后,四个涂色部分将全部+c;

然后我们去打补丁:将b[x1,y2+1]-=c,黄色和蓝色部分将-=c;将b[x2+1,y1]-=c,红色部分和蓝色部分将-=c;

然后发现蓝色部分多-=c,所以我们让b[x2+1,y2+1]+=c,那么蓝色部分将+=c;

大功告成,完整代码如下:

const int N = 1010;
int n, m, q;
int a[N][N];
void insert(int x1, int y1, int x2, int y2,int r)
{
	a[x1][y1] += r;
	a[x2 + 1][y2 + 1] += r;
	a[x1][y2 + 1] -= r;
	a[x2 + 1][y1] -= r;
}
int main()
{
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			int x;
			cin >> x;
			insert(i, j, i, j, x);
		}
	}
	while (q--)
	{
		int x1, y1, x2, y2,r;
		cin >> x1 >> y1 >> x2 >> y2 >> r;
		insert(x1, y1, x2, y2, r);
     }
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
			cout << a[i][j] << ' ';
		}
		cout << endl;
	}
	return 0;
}

以后将不定时更新这个系列,如果对你有帮助的话请点赞支持一下!

热门相关:开局签到荒古圣体   韩娱之影帝   这个大佬有点苟   试婚老公,要给力   试婚100天:夜少,轻轻宠