这个题有很多种做法 然后就可以练很多小的算法 技巧啥的嘿嘿
首先是模拟
要开一个为128+40为边长的数组 然后枚举在20~148内以(i,j)为中心的正方形 然后再挨个挨个计算sum
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define rg register 4 #define ll long long 5 const int N=200; 6 int n,d,mp[N][N]; 7 template<class t>void rd(t &x) 8 { 9 x=0;int w=0;char ch=0; 10 while(!isdigit(ch)) w|=ch=='-',ch=getchar(); 11 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 12 x=w?-x:x; 13 } 14 15 int main() 16 { 17 rd(d),rd(n); 18 int x,y,w,sum=0,mx=0,ans=1; 19 for(rg int i=1;i<=n;++i) rd(x),rd(y),rd(w),mp[x+20][y+20]=w; 20 for(rg int i=20;i<=148;++i) 21 for(rg int j=20;j<=148;++j) 22 { 23 for(rg int wi=i-d;wi<=i+d;++wi) 24 for(rg int wj=j-d;wj<=j+d;++wj) 25 sum+=mp[wi][wj];//以(i,j)为中心的矩阵的和 26 if(mx==sum) ++ans; 27 else if(mx<sum) ans=1,mx=sum; 28 sum=0; 29 } 30 printf("%d %d",ans,mx); 31 return 0; 32 }
然后是二位前缀和
求二位前缀和矩阵：
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];
以(x1,y1)为左上角 (x2,y2)为右下角的矩阵和
sum=a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1]
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define rg register 4 #define ll long long 5 const int N=129; 6 7 int a[200][200]; 8 9 template<class t>void rd(t &x) 10 { 11 x=0;int w=0;char ch=0; 12 while(!isdigit(ch)) w|=ch=='-',ch=getchar(); 13 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 14 x=w?-x:x; 15 } 16 17 int main() 18 { 19 int d,n,x,y,w; 20 memset(a,0,sizeof(a)); 21 rd(d),rd(n); 22 for(rg int i=1;i<=n;++i) rd(x),rd(y),rd(a[x+20][y+20]); 23 for(rg int i=20-d;i<=148+d;++i) 24 for(rg int j=20-d;j<=148+d;++j)//求矩阵前缀和 25 a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1]; 26 int sum,ans=1,mx=0; 27 for(rg int i=20;i<=148;++i) 28 for(rg int j=20;j<=148;++j) 29 {//sum为(i-d,j-d)为左上角,(i+d,j+d)为右下角的矩阵和 30 sum=a[i+d][j+d]-a[i+d][j-d-1]-a[i-d-1][j+d]+a[i-d-1][j-d-1]; 31 if(sum==mx) ++ans; 32 if(sum>mx) mx=sum,ans=1; 33 } 34 printf("%d %d",ans,mx); 35 return 0; 36 }
还有二维树状数组 倍增 我先咕了QAQ 哪天闲的蛋疼再来补