计蒜客 30991 - 2018 ICPC南京网络预赛 - B题 - The writing on the wall - 枚举计数

本文主要是介绍计蒜客 30991 - 2018 ICPC南京网络预赛 - B题 - The writing on the wall - 枚举计数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://nanti.jisuanke.com/t/30991

题意：有n*m的“1”矩阵，现将其中k个位置（x1,y1）~（xk，yk）的元素值变为“0”，问变换后的矩阵中有多少个不包含有“0”的矩阵。

解析：看到很多人说用单调队列做，具体做法可以看这篇博客https://blog.csdn.net/qq_42814118/article/details/81349964#commentBox

不过题目时限为2m，n*m*m的三重for循环（1e9）竟然能过QAQ。具体做法见代码。

暴力代码O(n*m*m)：

//3重for循环，1376ms
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3fLL
using namespace std;
const int maxn=1e5+10;int n,m,k;
int a[maxn][110],up[maxn];int main()
{int T,x,y,cas=1;scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) a[i][j]=1;up[i]=0;}for(int i=0;i<k;i++){scanf("%d%d",&x,&y);a[x][y]=0;}ll ans=0;//先注意左上角元素位置为(0,0)for(int i=1;i<=n;i++)//行{for(int j=1;j<=m;j++)//列if(!a[i][j]){up[j]=i;//up[j]对元素a[i][j]来说是同列上方最近“0”的行坐标.}for(int j=1;j<=m;j++)//枚举每个元素(i,j)，统计以其为右下角的矩形的个数.{int cnt=i;//cnt是宽为j-k+1的且以(i,j)其为右下角的矩形的高度；//也就是说cnt是宽为j-k+1的且以(i,j)其为右下角的矩形的个数.for(int k=j;k>=1;k--){cnt=min(cnt,i-up[k]);ans+=(ll)cnt;}}}printf("Case #%d: %lld\n",cas++,ans);}return 0;
}

单调队列代码O(n*m)：

枚举每个元素s[i][j]记录其往左的连续的“1”的个数num[i][j]，统计以该元素为右边缘的元素，且横向的长度<=num[i][j]子矩阵个数。单调栈维护往下和往上的对应高度。

#include <bits/stdc++.h>
#define R register
using namespace std;
typedef long long ll;
const ll Maxn=1e5+10;//num[i][j]是元素s[i][j]往左的连续的“1”的个数。
int n,m,k,s[Maxn][110],num[Maxn][110];
//sta为单调队列
int sta[Maxn],top,up[Maxn],down[Maxn];int main()
{int T,x,y,cas=1;scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&m,&k);for(R int i=1;i<=n;i++){for(R int j=1;j<=m;j++) s[i][j]=1;}for(R int i=0;i<k;i++){scanf("%d%d",&x,&y);s[x][y]=0;}for(R int i=1;i<=n;++i)for(R int j=1;j<=m;++j)num[i][j]=(s[i][j])?num[i][j-1]+1:0;R ll ans=0;for (R int j=1;j<=m;++j)//列{top = 0;for (R int i=1;i<=n;++i)//行{if(num[i][j]){//up[i]为元素s[i][j]当前列上面连续的num[][j]大于等于num[i][j]行数up[i]=1;while(top && num[i][j] <= num[sta[top]][j]) up[i]+=up[sta[top]],--top;sta[++top]=i;}else {top=0,up[i]=0;}}top = 0;for (R int i=n;i>=1;--i){if(num[i][j]){//down[i]为元素s[i][j]当前列下面连续的num[][j]大于等于num[i][j]行数down[i]=1;while(top && num[i][j] < num[sta[top]][j]) down[i]+=down[sta[top]],--top;sta[++top]=i;}else {top=0,down[i]=0;}ans += (ll)up[i]*down[i]*num[i][j];}}printf("Case #%d: %lld\n",cas++,ans);}return 0;
}

 

这篇关于计蒜客 30991 - 2018 ICPC南京网络预赛 - B题 - The writing on the wall - 枚举计数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---