本文共 1164 字，大约阅读时间需要 3 分钟。
这道题当时第一反应就是一道典型的NOIP第一题的难度，绝对要A掉，不然分数一定会被拉开。
然后就开始分析，暴力是一开始想的是用二维树状数组打加上暴力枚举长度，然而这道题满足二分性质，所以时间复杂度就是log n^3*n^2，还是会T然后就发现完全可以不用树状数组，直接n^2预处理统计起来然后log n* n^2二分答案并验证就可以了。大概从考试开始到打完不到17分钟吧，个人感觉还是可以的。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #define N 200511 using namespace std;12 int n,m,a[N][N],sum[N][N];13 bool check(int L)14 {15 int t=L*L;16 for(int i=L;i<=n;i++)17 {18 for(int j=L;j<=m;j++)19 {20 if(sum[i][j]-sum[i-L][j]-sum[i][j-L]+sum[i-L][j-L]==t)21 return 1;22 }23 }24 return 0;25 }26 int main()27 {28 scanf("%d%d",&n,&m);29 for(int i=1;i<=n;i++)30 {31 for(int j=1;j<=m;j++)32 {33 scanf("%d",&a[i][j]);34 }35 }36 for(int i=1;i<=n;i++)37 {38 for(int j=1;j<=m;j++)39 {40 sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j];41 }42 }43 int li=0,ri=min(n,m);44 while(li<=ri)45 {46 int mid=(li+ri)>>1;47 if(check(mid)) li=mid+1;48 else ri=mid-1;49 }50 printf("%d\n",li-1);51 return 0;52 }
转载于:https://www.cnblogs.com/liutianrui/p/7581745.html
