Wuyanru's blog
0%

[CF364E] Empty Rectangles

发表于 分类于 ，

神奇的题目。

之前看题解一直看不懂，直到最近发现少看了两行……

题目链接

题意

给定一个 的 矩阵，询问其有多少个子矩阵恰好包含 个 。

。

。

时限 。

题解

直接做看起来很不可行，考虑分治。

既然要分治，我们就要将整个矩形划为两部分，这里以横向划（划分为上下两部分）举例。

先来讲怎么计算跨过中线的答案，再来说优先横向划还是纵向划。

考虑枚举矩形的左右端点，这样我们就可以计算，对于矩形的上部分，上边界取到哪个范围时，上半部分恰好有 个 。

下半部分同理。

这样我们就可以双指针算出答案。

容易发现，这样对于第一层来说，复杂度是 的，显然不行。

如果套一个二分，就是 的，但是分治会再多一个 ，还是不行。

考虑能不能对于一个 ，同时算出所有 的答案。

对于一个固定的 ，我们容易在 的时间内算出 时的答案。

考虑能不能快速计算出 的答案。

之前的算法瓶颈在于计算上下边界的合法区间。

可以发现，此时的上边界，对比 时，会集体往下“掉”一段。

考虑暴力计算往下掉了多少。

对于同一个 来说，一共有 段边界，而每一段最多往下掉 的距离。

这样，对于一个固定的 ，我们的复杂度就是 。

所以分治一层的总复杂度就是 。

可以发现，复杂度瓶颈在于 （因为 代表矩形面积，不管横着划还是竖着划都是 的。

所以这告诉我们， 时应当将矩形划为上下两部分，否则划为左右两部分。

总复杂度为 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int pre[2505][2505];
char s[2505][2505];
char t[2505][2505];
char *ss[2505];
char *tt[2505];
int w1[11];
int w2[11];
int n,m,k;
inline int get(int u,int d,int l,int r)
{
    return pre[d][r]-pre[u-1][r]-pre[d][l-1]+pre[u-1][l-1];
}
inline ll run(char **s,char **t,int u,int d,int l,int r)
{
    if(r-l+1>d-u+1) return run(t,s,l,r,u,d);
    if(u==d)
    {
        if(s[u][l]=='0'&&k==0) return 1;
        if(s[u][l]=='1'&&k==1) return 1;
        return 0;
    }
    ll ans=0;int mid=(u+d)>>1;
    for(int i=u;i<=d;i++) for(int j=l;j<=r;j++)
    {
        pre[i][j]=s[i][j]-'0';
        pre[i][j]+=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];
    }

    for(int i=l;i<=r;i++)
    {
        for(int j=0;j<=k;j++) w1[j]=u,w2[j]=d;
        for(int j=i;j<=r;j++)
        {
            for(int p=0;p<=k;p++)
            {
                while(get(w1[p],mid,i,j)>p) w1[p]++;
                while(get(mid+1,w2[p],i,j)>p) w2[p]--;
            }
            // ll mem=ans;
            for(int p=0;p<=k;p++)
            {
                int tu=(p?w1[p-1]:mid+1)-w1[p];
                int td=w2[k-p]-(p!=k?w2[k-p-1]:mid);
                ans+=tu*td;
            }
            // printf("%d %d %d %d : i=%d j=%d : %lld\n",u,d,l,r,i,j,ans-mem);
        }
    }

    for(int i=u;i<=d;i++) for(int j=l;j<=r;j++) pre[i][j]=0;

    ans+=run(s,t,u,mid,l,r);
    ans+=run(s,t,mid+1,d,l,r);
    return ans;
}
int main()
{
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
    for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) t[i][j]=s[j][i];
    for(int i=1;i<=n;i++) ss[i]=s[i];
    for(int i=1;i<=m;i++) tt[i]=t[i];
    printf("%lld\n",run(ss,tt,1,n,1,m));
    return 0;
}

感谢观看！