补（前缀和）
领地选择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
说明/提示
样例解释
覆盖第一个地毯后：
| 00 | 00 | 00 | 00 | 00 |
|---|---|---|---|---|
| 00 | 11 | 11 | 00 | 00 |
| 00 | 11 | 11 | 00 | 00 |
| 00 | 00 | 00 | 00 | 00 |
| 00 | 00 | 00 | 00 | 00 |
覆盖第一、二个地毯后：
| 00 | 00 | 00 | 00 | 00 |
|---|---|---|---|---|
| 00 | 11 | 11 | 00 | 00 |
| 00 | 11 | 22 | 11 | 11 |
| 00 | 00 | 11 | 11 | 11 |
| 00 | 00 | 11 | 11 | 11 |
覆盖所有地毯后：
| 00 | 11 | 11 | 11 | 00 |
|---|---|---|---|---|
| 00 | 11 | 11 | 00 | 00 |
| 00 | 11 | 22 | 11 | 11 |
| 00 | 00 | 11 | 11 | 11 |
| 00 | 00 | 11 | 11 | 11 |
数据范围
对于?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;
}
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！