E - Defect-free Squares (atcoder.jp)
题意：一个H*W的矩形上有几个块有洞，问你没有洞的正方形有多少个
两种做法，DP和二分前缀和
DP是官方题解
先是二分前缀和做法，当时没想到前缀和可还行。。
先弄好前缀和，然后我们考虑用(i,j)作为正方形左上角能贡献多少个正方形，显然(i,j)作为左上角时最大正方形的边长就是答案，这里具有单增性，在这里入手
二分+前缀和
#include<iostream>
using namespace std;
bool mp[3005][3005];
int a[3005][3005];
int h,w,m,x,y;
long long ans;
bool check(int x,int y,int k)
{
return (a[x+k-1][y+k-1]-a[x+k-1][y-1]-a[x-1][y+k-1]+a[x-1][y-1])==0;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>h>>w>>m;
while(m--)
{
cin>>x>>y;
mp[x][y]=1;
}
for(register int i=1;i<=h;++i)
{
for(int j=1;j<=w;++j)
{
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+mp[i][j];
}
}
for(register int i=1;i<=h;++i)
{
for(int j=1;j<=w;++j)
{
if(mp[i][j])continue;
int l=0,r=min(h-i+1,w-j+1);
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(i,j,mid))l=mid;
else r=mid-1;
}
ans+=l;
}
}
cout<<ans;
return 0;
}然后是官方的DP做法，很巧妙
dp[i][j]是以(i,j)为右下角时，为答案贡献的正方形的个数。
如果想以图中黄色块为右下角，组成边长等于2的正方形的话，需要它上、左、左上均没有洞；如果要组成边长等于3的正方形的话，则需要绿色箭头指向的方向没有洞。
转移方程 当(i,j)没有洞的时候，dp[i][j]=min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1;
具体代码看官方题解即可
Editorial - Toyota Programming Contest 2023#4（AtCoder Beginner Contest 311）
标签：前缀,int,Defect,free,3005,正方形,Squares,dp From： https://www.cnblogs.com/qbning/p/17575065.html