题目

暂无

思路

一开始用四重循环，30％的数据会超时。后来我用类似前缀和的思路改进成三重循环，O（n³）通过。

代码

我的考场上的满分代码

#include<iostream>
#include<string.h>
using namespace std;
const int N =600+5;
int matrix[N][N];
int qianzhui[N][N];
int sum[N][N];
int main(){
    memset(qianzhui,0,sizeof(qianzhui);
    memset(sum,0,sizeof(sum);
       int n,r,L,t;
    cin>>n>>r>>L>>t;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>matrix[i][j];
        }
    }
    for(int i=0;i<n;i++){
        qianzhui[i][0] =matrix[i][0];
    }
    for(int i=0;i<n;i++){
        for(int j=1;j<n;j++){
            qianzhui[i][j]+=qianzhui[i][j-1]+matrix[i][j];
        }
    }
    for(int i=0;i<n;i++){
        int s =i-r>=0?i-r:0;
        int e =i+r<n?i+r:n-1;
        for(int j=0;j<n;j++){
            int s1=j-r>=0?j-r:0;
            int e1=j+r<n?j+r:n-1;
            for(int a =s1;a<e1;a++){
                if(s-1<0){
                    sum[i][j]+=qianzhui[a][e];
                }else{
                    sum[i][j]+=qianzhui[a][e]-qianzhui[a][s-1];
                }
            }
           sum[i][j]/=(e1-s1+1)*(e-s+1); 
        }
    }
    int count=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(sum[i][j]<=t){
                count++;
            }
        }
    }
     cout<<count;
     return 0;
}