做题思路

快速查询一个矩形区域钉子个数可以用二维前缀和实现，$4$ 层循环枚举左上和右下的坐标，复杂度 $O(n^2m^2)$ 会超时。

可以固定上下边界，滑动左右区间，可以用双指针，复杂度 $O(n^2m)$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,sum[505][505],ans;
char a[505][505];
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(a[i][j]=='#');
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			int l=1,r=1;
			while(r<=m){
				int cnt=sum[j][r]-sum[i-1][r]-sum[j][l-1]+sum[i-1][l-1];
				if(cnt<=1)ans+=(r-l+1),r++;
				else{
					l++;
					if(l>r)r=l;
				}
			}
		}
	}
	cout<<ans;
	return 0;
}

注意到二分可过，秒了。

时间复杂度 $O(n^3\ \log n)$，反正跑不满，显然是可以过的。

代码：

#include<bits/stdc++.h>
using namespace std;
int mp[505][505];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char d;
			cin>>d;
			mp[i][j]=d=='#';
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			mp[i][j]=mp[i-1][j]+mp[i][j-1]-mp[i-1][j-1]+mp[i][j];
		}
	}
	long long ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=i;k<=n;k++){
				int l=j,r=m,mid,lans=j;
				while(l<=r){
					mid=(l+r)>>1;
					if(mp[k][mid]-mp[k][j-1]-mp[i-1][mid]+mp[i-1][j-1]<=1){
						lans=mid;
						l=mid+1;
					}
					else{
						r=mid-1;
					}
				}
				if(lans==j && mp[k][j]-mp[k][j-1]-mp[i-1][j]+mp[i-1][j-1]>1){
					ans--;
				}
				ans+=lans-j+1;
			}
		}
	}
	cout<<ans;
	return 0;
}

补充思路。

如果一个区间计数问题，区间合法性质可以转化成一个条件是是否满足。

同时越扩大越糟糕（找最大可能方案），就可以用双指针。

像本题，如果问至少 k 个钉子，就应该把问题转换成总数 - 至多 k - 1 个钉子解决。