前缀和分为一维和二维，我现在才想起来，上次鸿哥在校赛A题上想要表达的那个意思就是一位前缀和
子段求和 ---- 一维前缀和
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define ll long long
using namespace std;
int sum[50001];
int main()
{
int n,m;
cin>>n;
int a,b;
for(int i=1;i<=n;i++){
cin>>a;
sum[i]=sum[i-1]+a;
}
cin>>m;
for(int i=0;i<m;i++){
cin>>a>>b;
printf("%d\n",sum[a+b-1]-sum[a-1]);//CARE!
}
return 0;
}
最大子矩阵 ---- 二维前缀和
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define ll long long
using namespace std;
int a[1001][1001];
int main()
{
//freopen("data","r",stdin);
int T,m,n,x,y;
cin>>T;
while(T--){
int maxi=-1;
memset(a,0,sizeof(a));
cin>>m>>n>>x>>y;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++){
cin>>a[i][j];
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
if(i>=x&&j>=y)
maxi=max(maxi,a[i][j]-a[i-x][j]-a[i][j-y]+a[i-x][j-y]);
}
cout<<maxi<<endl;}
return 0;
}
Color the ball
每次输入两个端点，我们把左端点的值加一，右端点右边的点的值减一，因为一个数出现的次数=以这个数为左端点的次数+这个数不是左端点的次数。左端点的值+1表示这个数是左端点，右端点右边的点的值-1代表这一段区间被这个点截断，那么这个点就不加进来了。比如说有两段区间：1到3和4到6，我们已经计算出了点3的出现次数为1，我们算4出现的次数的时候，一次是以4为起点的那个，再加上3出现的次数（为什么要加上3出现的次数呢，可以这样认为，因为我们其实是假设相邻两个数是同时出现的，如果不同时出现就会被后面的数截断）也就是1，这就是2次了，但是因为第一段区间被4截断了，所以还有减掉一次，所以就是一次了。合计合计c[i]就代表了该数字的最终出现次数。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a,b,c[100001];
int main()
{
int n;
while(cin>>n&&n>0){
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++){
cin>>a>>b;
c[a]++;
c[b+1]--;
}
for(int i=1;i<=n;i++){
c[i]+=c[i-1];
printf("%d%c",c[i],i==n?'\n':' ');
}
}
return 0;
}
中大代码
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > a;
int n,m;
void add(int x1,int y1,int x2,int y2) {
a[x1][y1]++;
a[x2+1][y2+1]++;
a[x1][y2+1]--;
a[x2+1][y1]--;
}
void solve() {
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]+a[i][j];
}
}
}
int main() {
ios::sync_with_stdio(0);
while(cin>>n>>m) {
a.clear();
a.resize(n+2,vector<int>(m+2,0));//值均为0
int p,q,x1,x2,y1,y2;
cin>>p;
while(p--) {
cin>>x1>>y1>>x2>>y2;
add(x1,y1,x2,y2);
}
solve();
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]) a[i][j]=1;
solve();
cin>>q;
while(q--) {
cin>>x1>>y1>>x2>>y2;
int L=(y2-y1+1)*(x2-x1+1);
int R=a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
if(L==R) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
}
网友评论