Codeforces 372B. Counting Rectangles is Fun【动态规划，暴力枚举】（lowbit()小用法）

101 阅读 0 评论 67 点赞

我是靠谱客的博主幸福樱桃，这篇文章主要介绍Codeforces 372B. Counting Rectangles is Fun【动态规划，暴力枚举】（lowbit()小用法），现在分享给大家，希望可以做个参考。

题目大意：

给出一个由0，1构成的矩阵，询问（a,b）到（c,d）两个点之间的只含有0的矩形有多少个。

方法：

由于矩阵不大，最多40*40，而且询问量很大（10^5）由此我们考虑o(1)输出答案，首先用一个四维数组预处理出答案，最后直接输出即可。

令dp[a][b][c][d]为（a,b）到（c,d）两个点之间的只含有0的矩形的数量，

则递推的公式：

dp[a][b][c][d]=dp[a][b][c][d-1]+dp[a][b][c-1][d]-dp[a][b][c-1][d-1]

每次计算在加上范围中含有（c，d）这个点的矩形即可。而计算含有（c，d）这个点的矩形，我们需要知道在每一行中，每个点离最近的1或者边界的距离，所以我们用一个数组row[i][j]在输入矩形的时候顺便记录（i,j）这个点离最近的1或者边界的距离。详细见代码和注释。

这里计算每个点离最近1或者边界的距离还有其他方法，当然都是听大牛说的。。

第一种：我们将每一行出现的1记录在vector中，每次寻找的时候，在vector中二分查找之前的最近的1或者边界。这样的话，我们算法的复杂度为在之前的复杂度上乘以一个logN，当然这里的N最大为40，其实可以忽略。

第二种：我们可以把每行输入的01010这样的串存为一个数字，求上面所说的距离的时候，我们需要知道的是第a行到第c行每一行中离第d列最近的1或者边界的距离，这样，我们可以在遍历第e行的时候（a<e<c）将该行对应的数字 右移d位，这样的话只要找到得到的 这个数字从右往左的第一个1在第几位即可（如果为0，说明第d列没有1），假设在第w位，那么 d-w就是我们上面所要求的距离。

但是问题来了，我们应该怎么求这个数字从右往左的第一个1在第几位呢？如果大家对 树状数组很熟悉的话，那一定会想起里面的 lowbit(i)函数,这个函数的实际意义不知道大家还记不记得，lowbit(i)=i&(-i)， 实际上，这个函数返回的值就是i值从右往左的第一个1所对应的值。假设i的二进制表示为11010100，那么-i的补码表示为：00101100（取反加1），当把两个数做按位与运算的时候，你会发现这样一个神奇的事实！ 那就是结果变成了00000100！这不正是我们想要的东西吗？虽然还不能直接用，但是稍微处理就能得到我们上面想要的 （d-w）了啊！

最后，我们可以弄一个数组，让我们可以o(1)的得到某个二次幂的数里面的1在第几位（比如说上面的100，bit[100]=bit[4]=2,bit使我们需要的数组），在这里N最大等于40。2的40次方是巨大的，这可不能直接扔到数组里面（不然这内存得要多大？。。。），但是想想，我们实际上只需要40个数，并不需要bit数组中的每个元素都用。 对！离散化咯！将二次幂的数取模（取模的数可以取99997,9997这些，只要40个数取模结果不会相同就行了~~），弄到一个散列中，那么我们就可以实现上面的功能啦~~

不得不说，这方法还真是有点妙啊~ym。。~

代码：

复制代码

#include <iostream>
#include <cstdio>
#define N 41
using namespace std;
int row[N][N],a[N][N],dp[N][N][N][N];
int main()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%1d",&a[i][j]);
            row[i][j]=row[i][j-1];//换行时，row[i][j]自动置为0；
            if(a[i][j]) row[i][j]=0;//遇到1，则置为0
            else row[i][j]++;
        }

for(int a=1;a<=n;a++)
        for(int b=1;b<=m;b++)
            for(int c=a;c<=n;c++)
                for(int d=b;d<=m;d++)
                {
                    dp[a][b][c][d]=dp[a][b][c][d-1]+dp[a][b][c-1][d]-dp[a][b][c-1][d-1];
                    int r=d-b+1;        //计算含有（c,d）这个点的矩形，当然尺寸不能超过该最大宽度
                    for(int e=c;e>=a;e--)
                    {
                        r=min(r,row[e][d]);
                        dp[a][b][c][d]+=r;
                    }
                }
    while(q--)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        cout<<dp[a][b][c][d]<<endl;
    }
    return 0;
}

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
#include <iostream>
#include <cstdio>
#define N 41
using namespace std;
int row[N][N],a[N][N],dp[N][N][N][N];
int main()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%1d",&a[i][j]);
            row[i][j]=row[i][j-1];//换行时，row[i][j]自动置为0；
            if(a[i][j]) row[i][j]=0;//遇到1，则置为0
            else row[i][j]++;
        }

    for(int a=1;a<=n;a++)
        for(int b=1;b<=m;b++)
            for(int c=a;c<=n;c++)
                for(int d=b;d<=m;d++)
                {
                    dp[a][b][c][d]=dp[a][b][c][d-1]+dp[a][b][c-1][d]-dp[a][b][c-1][d-1];
                    int r=d-b+1;        //计算含有（c,d）这个点的矩形，当然尺寸不能超过该最大宽度
                    for(int e=c;e>=a;e--)
                    {
                        r=min(r,row[e][d]);
                        dp[a][b][c][d]+=r;
                    }
                }
    while(q--)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        cout<<dp[a][b][c][d]<<endl;
    }
    return 0;
}