2020牛客暑期多校训练营（第九场）J.The Escape Plan of Groundhog

思路：枚举上下边界。先找到左右边框都是1的列，存在一个数组b里。
因为外边框要全是1，所以我们找到这个上下边界的连续的1的段，对每段都单独计算答案。
对每一段[l,r]而言，找到b数组的一个段，使得这些列都在[l,r]内。
然后我们枚举右边框，找有多少满足条件的左边框，这显然用一个数组记录一下前缀的矩形内部1，0差值就可以实现了。
时间复杂度$O(n^3)$

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define wzh(x) cerr<<#x<<'='<<x<<endl;
int n,m;
int a[555][555];
int s[555][555];
int vis[510*510*2];
int main() {
  ios::sync_with_stdio(false);
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      cin>>a[i][j];
      s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    }
  }
  auto get=[&](int x,int y,int dx,int dy){
    return s[dx][dy]-s[dx][y-1]-s[x-1][dy]+s[x-1][y-1];
  };
  vis[n*m+1]=1;
  LL ans=0;
  for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
      vector<int>v;
      for(int k=1;k<=m;k++){
        if(get(i,k,j,k)==j-i+1){
          v.pb(k);
        }
      }
      if(!(int)v.size()){
        continue;
      }
      int sz=v.size();
      int dx=1,dy=1;
      int idx=0;
      while(dx<=m&&dy<=m){
        if(a[i][dx]==0||a[j][dy]==0){
          dx++;
          dy++;
          continue;
        }
        int ddx=dx;
        int ddy=dy;
        while(ddx+1<=m&&a[i][ddx+1]==1&&
               ddy+1<=m&&a[j][ddy+1]==1){
          ddx++;
          ddy++;
        }
        while(idx<sz&&v[idx]<dx)idx++;
        if(idx==sz) {
          break;
        }
        if(v[idx]>ddx) {
          dx=ddx+1;
          dy=ddy+1;
          continue;
        }
        int nx=idx;
        while(nx+1<sz&&v[nx+1]<=ddx)nx++;
        if(nx==idx) {
          idx++;
          dx=ddx+1;
          dy=ddy+1;
          continue;
        }
        for(int g=idx+1;g<=nx;g++){
          int now=v[g];
          int sum=get(i,v[idx],j,now);//矩形内的1 边框全是1
          int zero=(j-i+1)*(now-v[idx]+1)-sum;
          int diff=sum-zero-2*(j-i+1)-2*(now-v[idx]+1)+4;//矩形内 不包括边框的 1 0 diff
          ans+=vis[n*m+1+diff]+vis[n*m+1+(diff-1)]+vis[n*m+1+(diff+1)];
         
          vis[n*m+1+diff+(j-i+1-2)]++;
        }
        for(int g=idx+1;g<=nx;g++){
          int now=v[g];
          int sum=get(i,v[idx],j,now);//矩形内的1 边框全是1
          int zero=(j-i+1)*(now-v[idx]+1)-sum;
          int diff=sum-zero-2*(j-i+1)-2*(now-v[idx]+1)+4;//矩形内 不包括边框的 1 0 diff
          vis[n*m+1+diff+(j-i+1-2)]--;
        }
        idx=nx+1;
        dx=ddx+1;
        dy=ddy+1;
      }
    }
  }
  cout<<ans<<'\n';
  return 0;
}

本文地址：https://blog.csdn.net/qq_40655981/article/details/107883355