补(前缀和)

2024-01-02 06:10:07

领地选择https://www.luogu.com.cn/problem/P2004

题目描述

作为在虚拟世界里统帅千军万马的领袖,小 Z 认为天时、地利、人和三者是缺一不可的,所以,谨慎地选择首都的位置对于小 Z 来说是非常重要的。

首都被认为是一个占地?�×�C×C?的正方形。小 Z 希望你寻找到一个合适的位置,使得首都所占领的位置的土地价值和最高。

输入格式

第一行三个整数?�,�,�N,M,C,表示地图的宽和长以及首都的边长。

接下来?�N?行每行?�M?个整数,表示了地图上每个地块的价值。价值可能为负数。

输出格式

一行两个整数?�,�X,Y,表示首都左上角的坐标。

输入输出样例

输入 #1复制

3 4 2
1 2 3 1
-1 9 0 2
2 0 1 1

输出 #1复制

1 2

说明/提示

对于?60%60%?的数据,�,�≤50N,M≤50。

对于?90%90%?的数据,�,�≤300N,M≤300。

对于?100%100%?的数据,1≤�,�≤1031≤N,M≤103,1≤�≤min?(�,�)1≤C≤min(N,M)。

思路:需要用到二维前缀和的知识,然后遍历每一个点就能过

#include<bits/stdc++.h>
#define itn int
using namespace std;
int a[1100][1100],sum[1100][1100];
long long   jisuan(int x1,int y1,int x2,int y2)
{
	long long  aa;
	aa=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
	return aa;
}
int main()
{
	int n,m,c;
	cin>>n>>m>>c;
	int idx,idy;
	long long  max=LLONG_MIN;
	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)
		{
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
		}
	}
	for (int x=1;x<=n-c+1;++x)
	{
		for (int y=1;y<=m-c+1;++y)
		{
			long long  aa=jisuan(x,y,x+c-1,y+c-1);
			if (aa>max)
			{
				max=aa;
				idx=x,idy=y;
			}
		}
	}
	cout<<idx<<" "<<idy;
}

kkksc03考前临时抱佛脚https://www.luogu.com.cn/problem/P2392

题目背景

kkksc03 的大学生活非常的颓废,平时根本不学习。但是,临近期末考试,他必须要开始抱佛脚,以求不挂科。

题目描述

这次期末考试,kkksc03 需要考?44?科。因此要开始刷习题集,每科都有一个习题集,分别有?�1,�2,�3,�4s1?,s2?,s3?,s4??道题目,完成每道题目需要一些时间,可能不等(�1,�2,…,��1A1?,A2?,…,As1??,�1,�2,…,��2B1?,B2?,…,Bs2??,�1,�2,…,��3C1?,C2?,…,Cs3??,�1,�2,…,��4D1?,D2?,…,Ds4??)。

kkksc03 有一个能力,他的左右两个大脑可以同时计算?22?道不同的题目,但是仅限于同一科。因此,kkksc03 必须一科一科的复习。

由于 kkksc03 还急着去处理洛谷的 bug,因此他希望尽快把事情做完,所以他希望知道能够完成复习的最短时间。

输入格式

本题包含?55?行数据:第?11?行,为四个正整数?�1,�2,�3,�4s1?,s2?,s3?,s4?。

第?22?行,为?�1,�2,…,��1A1?,A2?,…,As1???共?�1s1??个数,表示第一科习题集每道题目所消耗的时间。

第?33?行,为?�1,�2,…,��2B1?,B2?,…,Bs2???共?�2s2??个数。

第?44?行,为?�1,�2,…,��3C1?,C2?,…,Cs3???共?�3s3??个数。

第?55?行,为?�1,�2,…,��4D1?,D2?,…,Ds4???共?�4s4??个数,意思均同上。

输出格式

输出一行,为复习完毕最短时间。

输入输出样例

输入 #1复制

1 2 1 3		
5
4 3
6
2 4 3

输出 #1复制

20

说明/提示

1≤�1,�2,�3,�4≤201≤s1?,s2?,s3?,s4?≤20。

1≤�1,�2,…,��1,�1,�2,…,��2,�1,�2,…,��3,�1,�2,…,��4≤601≤A1?,A2?,…,As1??,B1?,B2?,…,Bs2??,C1?,C2?,…,Cs3??,D1?,D2?,…,Ds4??≤60。

思路:需要用到动态规划,给左脑分配总额一半的大小,使左脑尽可能的接近右脑,然后就可以得到右脑的时间,把所有的右脑加起来就是总时间

#include<bits/stdc++.h>
#define itn int
using namespace std;
int dp[2501],work[21],s[5];
int t;
int main()
{
	for(int i=1;i<=4;i++)
	{
		cin>>s[i];
	}
	for (int i=1;i<=4;++i)
	{
		int sum=0;
		for (int j=1;j<=s[i];++j)
		{
			cin>>work[j];
			sum+=work[j];
		}
		for (int j=1;j<=s[i];++j)
		{
			for(int k=sum/2;k>=work[j];k--)
				dp[k]=max(dp[k],dp[k-work[j]]+work[j]);
		}
		t+=sum-dp[sum/2];
		for (int k=1;k<=sum/2;++k)dp[k]=0;
	}
	cout<<t;
}

求区间和https://www.luogu.com.cn/problem/P8218

题目描述

给定?�n?个正整数组成的数列?�1,�2,??,��a1?,a2?,?,an??和?�m?个区间?[��,��][li?,ri?],分别求这?�m?个区间的区间和。

对于所有测试数据,�,�≤105,��≤104n,m≤105,ai?≤104

输入格式

第一行,为一个正整数?�n?。

第二行,为?�n?个正整数?�1,�2,??,��a1?,a2?,?,an?

第三行,为一个正整数?�m?。

接下来?�m?行,每行为两个正整数?��,��li?,ri??,满足1≤��≤��≤�1≤li?≤ri?≤n

输出格式

共?�m?行。

第?�i?行为第?�i?组答案的询问。

输入输出样例

输入 #1复制

4
4 3 2 1
2
1 4
2 3

输出 #1复制

10
5

说明/提示

样例解释:第?11?到第?44?个数加起来和为?1010。第?22?个数到第?33?个数加起来和为?55。

对于?50%50%?的数据:�,�≤1000n,m≤1000;

对于?100%100%?的数据:1≤�,�≤1051≤n,m≤105,1≤��≤1041≤ai?≤104

思路:一维前缀和

#include<bits/stdc++.h>
#define itn int
using namespace std;
itn n,m;
int a[100005],sum[100005];
int main()
{
	cin>>n; 
	for (int i=1;i<=n;++i)cin>>a[i];
	for (int i=1;i<=n;++i)sum[i]=sum[i-1]+a[i];
	cin>>m;
	for (int i=0;i<m;++i)
	{
		int l,r;
		cin>>l>>r;
		int s=sum[r]-sum[l-1];
		cout<<s<<endl;
	}
}

语文成绩https://www.luogu.com.cn/problem/P2367

题目背景

语文考试结束了,成绩还是一如既往地有问题。

题目描述

语文老师总是写错成绩,所以当她修改成绩的时候,总是累得不行。她总是要一遍遍地给某些同学增加分数,又要注意最低分是多少。你能帮帮她吗?

输入格式

第一行有两个整数?�n,�p,代表学生数与增加分数的次数。

第二行有?�n?个数,�1~��a1?~an?,代表各个学生的初始成绩。

接下来?�p?行,每行有三个数,�x,�y,�z,代表给第?�x?个到第?�y?个学生每人增加?�z?分。

输出格式

输出仅一行,代表更改分数后,全班的最低分。

输入输出样例

输入 #1复制

3 2
1 1 1
1 2 1
2 3 1

输出 #1复制

2

说明/提示

对于?40%40%?的数据,有?�≤103n≤103。

对于?60%60%?的数据,有?�≤104n≤104。

对于?80%80%?的数据,有?�≤105n≤105。

对于?100%100%?的数据,有?�≤5×106n≤5×106,�≤�p≤n,学生初始成绩?≤100≤100,�≤100z≤100。

思路:一维差分

#include<bits/stdc++.h>
#define itn int
using namespace std;
int n,p;
int s[5000005],b[5000005];
int x,y,z;
int main()
{
	cin>>n>>p;
	for(int i=1;i<=n;++i)cin>>s[i];
	for(int i=1;i<=n;++i)b[i]=s[i]-s[i-1];
	for (int i=0;i<p;++i)
	{
		cin>>x>>y>>z;
		b[x]+=z;
		b[y+1]-=z;	
	}	
	for (int i=1;i<=n;++i)b[i]+=b[i-1];
	int mins=110;
	for(int i=1;i<=n;++i)
	{
		if (mins>b[i])mins=b[i];
	}
	cout<<mins;
}

地毯https://www.luogu.com.cn/problem/P3397

题目描述

在?�×�n×n?的格子上有?�m?个地毯。

给出这些地毯的信息,问每个点被多少个地毯覆盖。

输入格式

第一行,两个正整数?�,�n,m。意义如题所述。

接下来?�m?行,每行两个坐标?(�1,�1)(x1?,y1?)?和?(�2,�2)(x2?,y2?),代表一块地毯,左上角是?(�1,�1)(x1?,y1?),右下角是?(�2,�2)(x2?,y2?)。

输出格式

输出?�n?行,每行?�n?个正整数。

第?�i?行第?�j?列的正整数表示?(�,�)(i,j)?这个格子被多少个地毯覆盖。

输入输出样例

输入 #1复制

5 3
2 2 3 3
3 3 5 5
1 2 1 4

输出 #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

说明/提示

样例解释

覆盖第一个地毯后:

0000000000
0011110000
0011110000
0000000000
0000000000

覆盖第一、二个地毯后:

0000000000
0011110000
0011221111
0000111111
0000111111

覆盖所有地毯后:

0011111100
0011110000
0011221111
0000111111
0000111111

数据范围

对于?20%20%?的数据,有?�≤50n≤50,�≤100m≤100。

对于?100%100%?的数据,有?�,�≤1000n,m≤1000。

思路:二维差分

#include<bits/stdc++.h>
#define itn int
using namespace std;
int a[1005][1005],b[1005][1005];
void insert(int x1,int y1,int x2,int y2,int c)
{
	b[x1][y1]+=c;
	b[x1][y2+1]-=c;
	b[x2+1][y1]-=c;
	b[x2+1][y2+1]+=c;
}
int main()
{
	int n,m;
	cin>>n>>m;
	for (int i=0;i<m;++i)
	{
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		insert(x1,y1,x2,y2,1);
	}
	for (int i=1;i<=n;++i)
	{
		for (int j=1;j<=n;++j)
		{
			b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+b[i][j];
		}
	}
	for (int i=1;i<=n;++i)
	{
		for (int j=1;j<=n;++j)
		{
			cout<<b[i][j]<<" ";
		}
		cout<<endl;
	}
}

Meteor Shower Shttps://www.luogu.com.cn/problem/P2895

题目描述

贝茜听说一场特别的流星雨即将到来:这些流星会撞向地球,并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑,发誓要找到一个安全的地方(一个永远不会被流星摧毁的地方)。

如果将牧场放入一个直角坐标系中,贝茜现在的位置是原点,并且,贝茜不能踏上一块被流星砸过的土地。

根据预报,一共有?�M?颗流星?(1≤�≤50,000)(1≤M≤50,000)?会坠落在农场上,其中第?�i?颗流星会在时刻?��Ti?(0≤��≤10000≤Ti?≤1000)砸在坐标为?(��,��)(0≤��≤300(Xi?,Yi?)(0≤Xi?≤300,0≤��≤300)0≤Yi?≤300)?的格子里。流星的力量会将它所在的格子,以及周围?44?个相邻的格子都化为焦土,当然贝茜也无法再在这些格子上行走。

贝茜在时刻?00?开始行动,她只能在第一象限中,平行于坐标轴行动,每?11?个时刻中,她能移动到相邻的(一般是?44?个)格子中的任意一个,当然目标格子要没有被烧焦才行。如果一个格子在时刻?�t?被流星撞击或烧焦,那么贝茜只能在?�t?之前的时刻在这个格子里出现。 贝茜一开始在?(0,0)(0,0)。

请你计算一下,贝茜最少需要多少时间才能到达一个安全的格子。如果不可能到达输出??1?1。

输入格式

共?�+1M+1?行,第?11?行输入一个整数?�M,接下来的?�M?行每行输入三个整数分别为?��,��,��Xi?,Yi?,Ti?。

输出格式

贝茜到达安全地点所需的最短时间,如果不可能,则为??1?1。

输入输出样例

输入 #1复制

4
0 0 2
2 1 2
1 1 2
0 3 5

输出 #1复制

5

思路:BFS搜,只需要在陨石落下来之前走到就ok了

#include<bits/stdc++.h>
using namespace std;
struct Queue{
	int x;
	int y;
	int s;
};
int a[305][305],vis[305][305];
struct Queue queue1[1000005];
int main()
{
	int m;
	cin>>m;
	int move[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
	for(int i=0; i<=302; i++)
		for(int j=0; j<=302; j++)
			a[i][j]=-1; 
	for (int i=0;i<m;++i)
	{
		int x1,y1,s1;
		cin>>x1>>y1>>s1;
		if (a[x1][y1]==-1 || s1<a[x1][y1])a[x1][y1]=s1;
		for (int i=0;i<=3;++i)
		{
			int x2=x1+move[i][0],y2=y1+move[i][1];
			if (x2<0||y2<0)continue;
			if (a[x2][y2]==-1 || s1<a[x2][y2]) a[x2][y2]=s1;
		}
	}
	int head=0,tail=0;
	queue1[tail].x=0,queue1[tail].y=0,queue1[tail].s=0;
	vis[0][0]=1;
	tail++;
	while (head!=tail)
	{
		int x=queue1[head].x,y=queue1[head].y,s=queue1[head].s;
		for (int i=0;i<=3;++i)
		{
			int tx=x+move[i][0],ty=y+move[i][1];
			if (tx<0||ty<0)continue;
			if ((a[tx][ty]>s+1 || a[tx][ty]==-1) && vis[tx][ty]==0)
			{
				queue1[tail].x=tx,queue1[tail].y=ty,queue1[tail].s=s+1;
				vis[tx][ty]=1;
				tail++;
				if (a[tx][ty]==-1)
				{
					cout<<s+1<<endl;
					return 0;
				}
			}
		}
		head++;
	
	}
	cout<<-1;
}

文章来源:https://blog.csdn.net/2301_80489323/article/details/135330694
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。