csp：202104-2：邻域均值

这道题可以用最简单的方式：四层遍历暴力求解，不过稍微计算一下时间复杂度就会发现这绝对超时。

实际上，这道题略微有一点滑动窗口的思想，通过不断更新窗口来求解，可以将算法的时间复杂度降低到题目要求。

100分代码：

#include<iostream>

using namespace std;

int n,L,r,t;
int A[605][605];

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>L>>r>>t;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cin>>A[i][j];
    }
  }
  int res=0;
  for(int i=0;i<n;i++){
    int neighbor=-1;
    int min_x,min_y,max_x,max_y;
//    int pre_min_x,pre_min_y,pre_max_x,pre_max_y;
    for(int j=0;j<n;j++){
//      pre_min_x=min_x;
//      pre_min_y=min_y;
//      pre_max_x=max_x;
//      pre_max_y=max_y;
      
      min_y=max(0,i-r);
      max_y=min(n-1,i+r);
      min_x=max(0,j-r);
      max_x=min(n-1,j+r);
      
      if(neighbor>=0){
        if(j+r<=n-1){// 看是否新引入一列A 
          for(int y=min_y;y<=max_y;y++){
            neighbor+=A[y][max_x];
          } 
        } 
        if(min_x>0){// 看是否需要删掉旧的一列A
          for(int y=min_y;y<=max_y;y++){
            neighbor-=A[y][min_x-1];
          } 
        }
        
      }else{ // 重新计算neighbor 
        neighbor=0;
        for(int a1=min_y;a1<=max_y;a1++){
          for(int a2=min_x;a2<=max_x;a2++){
            neighbor+=A[a1][a2];
          }
        } 
      }
      if(neighbor<=t*(max_x-min_x+1)*(max_y-min_y+1)){
        res++;
      }
//      cout<<neighbor<<' ';
    } 
//    cout<<endl;
  }
  cout<<res;
}