虔诚的墓主人(BZOJ1227)(洛谷P2154)解题报告

题目描述

小W是一片新造公墓的管理人。公墓可以看成一块N×M的矩形,矩形的每个格点,要么种着一棵常青树,要么是一块还没有归属的墓地。

当地的居民都是非常虔诚的基督徒,他们愿意提前为自己找一块合适墓地。为了体现自己对主的真诚,他们希望自己的墓地拥有着较高的虔诚度。

一块墓地的虔诚度是指以这块墓地为中心的十字架的数目。一个十字架可以看成中间是墓地,墓地的正上、正下、正左、正右都有恰好k棵常青树。

小W希望知道他所管理的这片公墓中所有墓地的虔诚度总和是多少。

输入输出格式

输入格式:

输入文件religious.in的第一行包含两个用空格分隔的正整数N和M,表示公墓的宽和长,因此这个矩形公墓共有(N+1) ×(M+1)个格点,左下角的坐标为(0, 0),右上角的坐标为(N, M)。

第二行包含一个正整数W,表示公墓中常青树的个数。

第三行起共W行,每行包含两个用空格分隔的非负整数xi和yi,表示一棵常青树的坐标。输入保证没有两棵常青树拥有相同的坐标。

最后一行包含一个正整数k,意义如题目所示。

输出格式:

输出文件religious.out仅包含一个非负整数,表示这片公墓中所有墓地的虔诚度总和。为了方便起见,答案对2,147,483,648取模。

输入输出样例

输入样例#1:
5 6
13
0 2
0 3
1 2
1 3
2 0
2 1
2 4
2 5
2 6
3 2
3 3
4 3
5 2
2
输出样例#1:
6
虔诚的墓主人(BZOJ1227)(洛谷P2154)解题报告
题目描述摘自洛谷。



非常幸运过了这道生涯题,从上午10:30到晚上20:15。事实证明,人应该对自己有点信心,应该有点梦想,万一就见鬼了呢。
题目大意,给出一个N*M的方格,在每个点上分布着常青树/墓地,我们需要统计每个墓地的虔诚度,相加求得答案。
题中描述的是“恰好”有k颗树,看一眼样例,发现事情没那么简单,再结合答案,很容易分析出我们应该求的是每个点上下左右对应的组合数相乘。
由乘法原理可知,我们要求的是从上下左右的常青树中分别选出k颗,对应的方案数乘乘积。
虔诚的墓主人(BZOJ1227)(洛谷P2154)解题报告(L,R,U,D分别代表Left,Right,Up,Down)
观察数据范围,k <= 10,由杨辉三角行列数对应组合数,我们可以通过杨辉三角递推式,预处理出所有的组合数。
然而再看一眼数据范围,N,M的范围过大,不用说线性递推,数组都开不下。然而常青树W的个数却只有100,000个,考虑离散化。
在离散化的过程中,顺手处理出每行每列的常青树个数。(后面在解释)。
至此,预处理的所有工作已经完成,放个代码。(码风丑,请见谅)
离散化:(1倍存原数,2倍存x,3倍存y)
inline void discretizition()
{
    scanf("%d%d%d",&n,&m,&w);
    for(int i = 1;i<=w;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        nd[i+w].temp = x;
        nd[i+w].kind = 1;
        nd[i+w].num = i;
        nd[i+2*w].temp = y;
        nd[i+2*w].kind = 2;
        nd[i+2*w].num = i;
    }            
    int cnt = 1;
    sort(nd+w+1,nd+3*w+1,cmp1);
    for(int i = w+1;i<=3*w;i++)
    {
        if(i==w+1)
        {
            int num = nd[i].num;
            if(nd[i].kind==1)
            {
                nd[num].x = cnt;
                lie[cnt]++;    //列数
            }else
            {
                nd[num].y = cnt;
                hang[cnt]++;    //行数
            }
            continue;
        }
        if(nd[i].temp!=nd[i-1].temp)cnt++;
        int num = nd[i].num;
        if(nd[i].kind==1)
        {
            nd[num].x = cnt;
            lie[cnt]++;  //列数
        }else
        {
            nd[num].y = cnt;
            hang[cnt]++;    //行数
        }
    }
}

递推杨辉三角,预处理组合数:
inline void getC()
{
    scanf("%d",&k);
    C[0][0] = 1;
    for(int i = 1;i<=W;i++)
    {
        for(int j = 0;j<=10;j++)
        {
            if(j==0){C[i][j] = 1;continue;}
            C[i][j] = (C[i-1][j-1]+C[i-1][j])&mod;
        }
    }
}

明确一点小技巧,取模2147483648和按位与2147483647效果是一样的。(1<<31==2147483648)
如果还不明白,请实践几组数,或者仔细想想。毕竟脑袋是用来想的,不是用来装饰的。
当我们完成预处理步骤时,我们已经将整个方格缩小到了100,000×100,000的大小了,接下来便是如何计算虔诚度。
暴力枚举墓地?必然超时(但是洛谷数据貌似可以通过一些玄学优化方法过掉,这里暂不提及)。我们需要找到一种更为快速的方法。
When you have eliminated the impossibles,whatever remains,however improbable,must be the truth.——福尔摩斯
我们希望能出现O(wlog)的方法,或者O(w)的方法。由于常青树一共只有100,000颗,既然我们不能枚举墓地,不妨枚举常青树。
而枚举常青树又不能随意枚举,不然在累积虔诚度的时候又会变成w方的情况,我们需要一些数据结构来维护虔诚度,如何维护?维护什么?这就是本题的关键。
经过我们的一番分析(标签)我们知道本题使用的数据结构是树状数组。
不要问我怎么分析出来的树状数组,我就是看到它是树状数组才决定的做这道题。
我们在枚举的过程中,想要求的是每个空地上下左右组合数的乘积,可以发现在同一行(列)(以下统一为行)两颗常青树之间的空地,它们左面和右面常青树的组合数是相同的。
这也就给了我们灵感,我们可以通过有顺序的枚举,确定一维,转移一维。这时候需要把所有点按照行优先,列其次的顺序排序。这样枚举的时候就是有序的了。
再瞅一眼图,找找感觉。
虔诚的墓主人(BZOJ1227)(洛谷P2154)解题报告
假定现在我们枚举到了蓝色点,我们在枚举的时候可以通过前后点是否在同一行,定义变量来记录这一行已经枚举了多少颗常青树,再通过这一行常青树的总数,
减去左方的常青树,即可得到右方的常青树,左右的组合数乘积即可轻松得到。这也就是之前要维护每一行常青树个数的原因。
那么如何快速计算同一行两颗常青树之间墓地的虔诚度之和?
上面的图没有同一行连续的墓地,我们把它转90°(awa)。
虔诚的墓主人(BZOJ1227)(洛谷P2154)解题报告
好,现在在下数起第三行,出现了两个蓝色点,它们左右的常青树数量相同。
不妨设L为两个蓝色点左边组合数,R为两个蓝色点右边组合数,U1为1号蓝色点上方组合数,D1为其下方组合数,U2同理为2号蓝色点上方组合数,D2为蓝色点下方组合数。
我们要求的这两个点的虔诚度为:
Ans = L×R×U1×D1 + L×R×U2×D2
= L×R×(U1×D1 + U2×D2)
看到这里,您应该已经猜到如何快速计算墓地虔诚度的和了。
树状数组里面存的不是常青树个数,我们将每一列的列数作为树状数组的下标,将这一列在本时刻所对应的上下组合数的乘积存入树状数组中,再通过前缀和相减,
算出两颗常青树之间的墓地的上下组合数乘积之和。
对应上方例子,即树状数组四号点存储的是U1×D1,五号点存储的是U2×D2,所求虔诚度:
Ans = L×R×(getsum(5)-getsum(4-1));
在算完两棵树之间的墓地后,需要更新对应列的树状数组中的值,更新的值即为重新算出的组合数与之前的组合数之差,对应例子中,4号点应该更新的值即为:
Update(4,(U1-1)×(D1+1)-U1×D1);
5号点同理。
这里的D1/U1可以通过枚举顺序记录,作者通过自下而上枚举,所以通过数组记录了D1,之前又记录了每一列的常青树个数,相减即可得到U1。
逐渐枚举,更新答案即可。
换行或两颗常青树相邻的情况读者自行思考即可,除此以外最好将行列数坐标+1,因原题中原点为(0,0),树状数组更新不便。
Talk is cheap,show me the code。
#include<cstdio>
#include<algorithm>
#define W 100005
#define mod 2147483647
#define ll long long
using namespace std;
int n,m,w,lie[2*W+1],hang[2*W+1],k,tree[2*W],down[2*W];
ll C[2*W+1][12];
ll ans;
struct node
{
    int x,y,num,kind,temp;
}nd[W*3+2];
inline bool cmp1(node a,node b)
{
    return a.temp<b.temp;
}
inline bool cmp(node a,node b)
{
    if(a.y!=b.y)
    {
        return a.y<b.y;
    }else
    {
        return a.x<b.x;
    }
}
inline void discretizition()
{
    scanf("%d%d%d",&n,&m,&w);
    for(int i = 1;i<=w;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        nd[i+w].temp = x;
        nd[i+w].kind = 1;
        nd[i+w].num = i;
        nd[i+2*w].temp = y;
        nd[i+2*w].kind = 2;
        nd[i+2*w].num = i;
    }            
    int cnt = 1;
    sort(nd+w+1,nd+3*w+1,cmp1);
    for(int i = w+1;i<=3*w;i++)
    {
        if(i==w+1)
        {
            int num = nd[i].num;
            if(nd[i].kind==1)
            {
                nd[num].x = cnt;
                lie[cnt]++;    
            }else
            {
                nd[num].y = cnt;
                hang[cnt]++;    
            }
            continue;
        }
        if(nd[i].temp!=nd[i-1].temp)cnt++;
        int num = nd[i].num;
        if(nd[i].kind==1)
        {
            nd[num].x = cnt;
            lie[cnt]++;
        }else
        {
            nd[num].y = cnt;
            hang[cnt]++;    
        }
    }
}
inline void getC()
{
    scanf("%d",&k);
    C[0][0] = 1;
    for(int i = 1;i<=W;i++)
    {
        for(int j = 0;j<=10;j++)
        {
            if(j==0)
            {
                C[i][j] = 1;
                continue;
            }
            C[i][j] = (C[i-1][j-1]+C[i-1][j])&mod;
        }
    }
}
inline int lowbit(int x)
{
    return x&(-x);
}
inline void update(int pos,int x)
{
    for(int i = pos;i<=w;i+=lowbit(i))
    {
        tree[i]+=x;
    }
}
inline ll getsum(int pos)
{
    ll tmp = 0;
    for(int i = pos;i;i-=lowbit(i))
    {
        tmp=(tmp+tree[i])&mod;
    }
    return tmp&mod;
}
inline void solve()
{
    sort(nd+1,nd+1+w,cmp);
    int tot = 0;
    for(int i = 1;i<=w;i++)
    {
        if(i==1)
        {
            tot++;
            down[nd[i].x]++;
            update(nd[i].x,(C[down[nd[i].x]][k]*C[lie[nd[i].x]-down[nd[i].x]][k])&mod);
            continue;
        }
        if(nd[i].y==nd[i-1].y)
        {
            tot++;
            if((tot-1>=k)&&(hang[nd[i].y]-tot+1>=k))
            {
                ll tp = getsum(nd[i].x-1)-getsum(nd[i-1].x);
                tp = tp*C[hang[nd[i].y]-tot+1][k]*C[tot-1][k]&mod;
                ans = (ans+tp)&mod;
            }
            down[nd[i].x]++;
            update(nd[i].x,(C[down[nd[i].x]][k]*C[lie[nd[i].x]-down[nd[i].x]][k]&mod)-(C[down[nd[i].x]-1][k]*C[lie[nd[i].x]-down[nd[i].x]+1][k]&mod));            
        }else
        {
            down[nd[i].x]++;
            update(nd[i].x,(C[down[nd[i].x]][k]*C[lie[nd[i].x]-down[nd[i].x]][k]&mod)-(C[down[nd[i].x]-1][k]*C[lie[nd[i].x]-down[nd[i].x]+1][k]&mod));
            tot = 1;
        }
    }
    printf("%lld\n",ans&mod);
}
int main()
{
    discretizition();
    getC();
    solve();
    return 0;
}

 

 

 

 

 



 

 

 

 

  

 

 


上一篇:CF452F Permutations/Luogu2757 等差子序列 树状数组、Hash


下一篇:4.算法调试