• [bzoj1227]虔诚的墓主人


    题目描述

    小W 是一片新造公墓的管理人。公墓可以看成一块N×M 的矩形,矩形的每个格点,要么种着一棵常青树,要么是一块还没有归属的墓地。当地的居民都是非常虔诚的基督徒,他们愿意提前为自己找一块合适墓地。为了体现自己对主的真诚,他们希望自己的墓地拥有着较高的虔诚度。一块墓地的虔诚度是指以这块墓地为中心的十字架的数目。一个十字架可以看成中间是墓地,墓地的正上、正下、正左、正右都有恰好k 棵常青树。小W 希望知道他所管理的这片公墓中所有墓地的虔诚度总和是多少

    输入格式

    第一行包含两个用空格分隔的正整数N 和M,表示公墓的宽和长,因此这个矩形公墓共有(N+1) ×(M+1)个格点,左下角的坐标为(0, 0),右上角的坐标为(N, M)。第二行包含一个正整数W,表示公墓中常青树的个数。第三行起共W 行,每行包含两个用空格分隔的非负整数xi和yi,表示一棵常青树的坐标。输入保证没有两棵常青树拥有相同的坐标。最后一行包含一个正整数k,意义如题目所示。

    输出格式

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

    样例

    样例输入

    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

    样例输出

    6

    数据范围与提示

    图中,以墓地(2, 2)和(2, 3)为中心的十字架各有3个,即它们的虔诚度均为3。其他墓地的虔诚度为0。 所有数据满足1 ≤ N, M ≤ 1,000,000,000,0 ≤ xi ≤ N,0 ≤ yi ≤ M,1 ≤ W ≤ 100,000, 1 ≤ k ≤ 10。存在50%的数据,满足1 ≤ k ≤ 2。存在25%的数据,满足1 ≤ W ≤ 10000。 注意:”恰好有k颗树“,这里的恰好不是有且只有,而是从>=k的树中恰好选k棵

    25%算法:

    要求选法,k<=10 杨辉三角打组合数表

    n m很大,但w较小,稀疏图。由于k>=1所以无树的坐标直线无贡献,直接离散化,这样得到了最坏情况为w*w的图。然后脑残O(w^2)算一波前缀和,放到四个w^2数组里,再O(w^2)直接扫算贡献。。。

    局限:空间复杂度太高O(5w^2)最多卡10000,时间O(w^2)

      1 #include<cstdio>
      2 #include<algorithm>
      3 #include<cmath>
      4 #include<cstring>
      5 //#define MAXN 1000005
      6 #define MAXK 11
      7 #define MAXW 10005
      8 #define ll long long
      9 #define reg register
     10 #define F(i,a,b) for(i=a;i<=b;++i)
     11 using namespace std;
     12 //对图离散化,因为k>=1,所以在某坐标直线上无树则无贡献
     13 ll c[MAXW][MAXK];
     14 ll mod=2147483647;
     15 int H[MAXW],L[MAXW],e[MAXW][MAXW],hs[MAXW][MAXW],ls[MAXW][MAXW],la[105][105],n,m,cx,cy;
     16 int read()
     17 {
     18     reg char c; reg int x=0;
     19     c=getchar();
     20     while(c<'0'||c>'9') c=getchar();
     21     while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
     22     return x;
     23 }
     24 struct POINT{
     25     int x,y;
     26 }p[MAXW];
     27 void debug()
     28 {
     29     reg int i,j;
     30     F(i,0,n)
     31     {
     32         F(j,0,m)
     33         {
     34             printf("%d ",la[i][j]);
     35         }
     36         puts("");
     37     }
     38     puts("");
     39     F(i,1,cx)
     40     {
     41         F(j,1,cy)
     42         {
     43             printf("%d ",hs[i][j]);
     44         }
     45         puts("");
     46     }
     47     puts("");
     48     F(i,1,cx)
     49     {
     50         F(j,1,cy)
     51          {
     52              printf("%d ",ls[i][j]);
     53         }
     54         puts("");
     55     }
     56 }
     57 int main()
     58 {
     59     int W,u; reg int i,j;
     60     mod++;
     61     n=read(); m=read(); W=read();
     62     F(i,1,W) 
     63         p[i].x=H[i]=read(),p[i].y=L[i]=read();
     64     sort(H+1,H+W+1);            sort(L+1,L+W+1);
     65     cx=unique(H+1,H+W+1)-H-1;     cy=unique(L+1,L+W+1)-L-1;
     66     F(i,1,W)
     67     {
     68 //        la[p[i].x][p[i].y]=1;
     69         p[i].x=lower_bound(H+1,H+cx+1,p[i].x)-H;
     70         p[i].y=lower_bound(L+1,L+cy+1,p[i].y)-L;
     71          e[p[i].x][p[i].y]=1;
     72     }
     73     u=read();
     74     c[0][0]=1;
     75     F(i,1,n)
     76     {
     77         c[i][0]=1;
     78         F(j,1,min(i,u)) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
     79     }
     80     F(i,1,cx)
     81     {
     82         F(j,1,cy)
     83         {
     84             hs[i][j]=hs[i][j-1]+e[i][j];
     85             ls[i][j]=ls[i-1][j]+e[i][j];
     86         }
     87     }
     88     reg int w,a,s,d;
     89     reg ll ans=0;
     90     F(i,1,cx)
     91     {
     92         F(j,1,cy)
     93         {
     94             if(e[i][j]) continue;
     95             w=hs[i][j]; a=ls[i][j]; s=ls[cx][j]-ls[i][j]; d=hs[i][cy]-hs[i][j];
     96             if(w<u||a<u||s<u||d<u) continue;
     97 //            printf("%d %d %d %d %d %d
    ",i,j,w,a,s,d);
     98 //            printf("    %lld %lld %lld %lld
    ",c[w][u],c[a][u],c[s][u],c[d][u]);
     99             ans=(ans+c[w][u]*c[a][u]%mod*c[s][u]%mod*c[d][u]%mod)%mod;
    100         }
    101     }
    102 //    printf("%lld",c[4][2]);
    103 //    debug();
    104     printf("%lld",ans);
    105     return 0;
    106 }
    View Code

    60%算法:

    针对于上面的局限,考虑把平面问题转化为线性,优化aa[]...的预处理。

    首先在离散化时顺带处理出每行每列的总树数 hs[] ls[],然后对所有树以x为第一关键字,y为第二关键字排序,这样O(w)扫描满足拓扑序直接统计即可。

    然后再O(w)扫,知有贡献的墓地一定在同一行且两侧常青树>=k的段(但不一定满足列)中,每段的贡献为Σ(c[j上][k]*c[j下][k])*c[j左][k]*c[j右][k],j在同一行的两棵常青树中。

    局限:时间复杂度(w^2)

    100%算法:

    不难发现上面的柿子可以用前缀和优化,由于带修用树状数组。

    树状数组维护前i列的Σ(c[j上][k]*c[j下][k]),每扫到树更新当前列即可。由此复杂度优化到O(wlogw)。

    常数黑科技优化,对2^32取模,可以用unsigned int对2^64自然溢出,最后输出再%2^32。

    WA因:

    1 if(ww[i]>=u&&ss[i]-1>=u)
    2         {
    3             add(p[i].y,-wl[p[i].y]);
    4             add(p[i].y,c[ww[i]][u]*c[ss[i]-1][u]);
    5             wl[p[i].y]=c[ww[i]][u]*c[ss[i]-1][u];
    6         }

    若此树是该列的第一棵不能做出贡献的树,则未将其列贡献清零。

     1 #include<cstdio>
     2 #include<algorithm>
     3 #include<cmath>
     4 #include<cstring>
     5 #define MAXK 11
     6 #define MAXW 100005
     7 #define un unsigned
     8 #define ll long long
     9 #define reg register
    10 #define F(i,a,b) for(i=a;i<=b;++i)
    11 using namespace std;
    12 un int c[MAXW][MAXK],tr[MAXW];
    13 ll mod=2147483647;
    14 int H[MAXW],L[MAXW],hs[MAXW],ls[MAXW],n,m,cx,cy,ww[MAXW],aa[MAXW],ss[MAXW],dd[MAXW],htot[MAXW],ltot[MAXW],W;
    15 un int wl[MAXW];
    16 int read()
    17 {
    18     reg char c; reg int x=0;
    19     c=getchar();
    20     while(c<'0'||c>'9') c=getchar();
    21     while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
    22     return x;
    23 }
    24 struct POINT{
    25     int x,y;
    26     friend bool operator<(POINT a,POINT b)
    27     {
    28         return a.x==b.x?a.y<b.y:a.x<b.x;
    29     }
    30 }p[MAXW];
    31 void add(int x,un int w)
    32 {
    33     while(x<=W)
    34     {
    35         tr[x]+=w;
    36         x+=(x&-x);
    37     }
    38 }
    39 un int get(int x)
    40 {
    41     reg un int ans=0;
    42     while(x>0)
    43     {
    44         ans+=tr[x];
    45         x-=(x&-x);
    46     }
    47     return ans;
    48 }
    49 int main()
    50 {
    51     int u; reg int i,j;
    52     mod++;
    53     n=read(); m=read(); W=read();
    54     F(i,1,W) p[i].x=H[i]=read(),p[i].y=L[i]=read();
    55     sort(H+1,H+W+1);            sort(L+1,L+W+1);
    56     cx=unique(H+1,H+W+1)-H-1;     cy=unique(L+1,L+W+1)-L-1;
    57     F(i,1,W)
    58     {
    59         p[i].x=lower_bound(H+1,H+cx+1,p[i].x)-H;
    60         p[i].y=lower_bound(L+1,L+cy+1,p[i].y)-L;
    61          ++htot[p[i].x];
    62         ++ltot[p[i].y];
    63     }
    64     u=read();
    65     sort(p+1,p+W+1);
    66     c[0][0]=1;
    67     F(i,1,W)
    68     {
    69         c[i][0]=1;
    70         F(j,1,min(i,u)) c[i][j]=c[i-1][j]+c[i-1][j-1];
    71     }
    72     F(i,1,W)
    73     {
    74         ss[i]=ltot[p[i].y]-ls[p[i].y];
    75         dd[i]=htot[p[i].x]-hs[p[i].x];
    76         ww[i]=++ls[p[i].y];
    77         aa[i]=++hs[p[i].x];
    78     }
    79     reg un int ans=0;
    80     F(i,1,W)
    81     {
    82         add(p[i].y,-wl[p[i].y]);
    83         add(p[i].y,c[ww[i]][u]*c[ss[i]-1][u]);
    84         wl[p[i].y]=c[ww[i]][u]*c[ss[i]-1][u];
    85         if(p[i-1].x==p[i].x&&aa[i]-1>=u&&dd[i]>=u)
    86             ans+=(get(p[i].y-1)-get(p[i-1].y))*c[aa[i]-1][u]*c[dd[i]][u];
    87     }
    88     printf("%lld",ans%mod);
    89     return 0;
    90 }
    AC

    PS:第一次对拍 存板

     1 #include<cstdio>
     2 #include<algorithm>
     3 #include<ctime>
     4 #include<cstring>
     5 //#define MAXN 1000005
     6 #define MAXK 11
     7 #define MAXW 100005
     8 #define un unsigned
     9 #define ll long long
    10 #define reg register
    11 #define F(i,a,b) for(i=a;i<=b;++i)
    12 using namespace std;
    13 
    14 int main()
    15 {
    16     reg double t1,t2;
    17     while(1)
    18     {
    19         system("./data.out");
    20         system("./std.out");
    21         t1=clock();
    22         system("./a.out");
    23         t2=clock();
    24         if(system("diff std.ans a.ans"))
    25         {
    26             printf("WA %lfms
    ",(t2-t1));
    27             return 0;
    28         }
    29         else printf("AC %lfms
    ",(t2-t1));
    30     }
    31     return 0;
    32 }
    对拍
     1 #include<cstdio>
     2 #include<cstdlib>
     3 #include<algorithm>
     4 #include<ctime>
     5 #include<cstring>
     6 #define MAXN 30000
     7 #define MAXK 10
     8 #define MAXW 100000
     9 #define un unsigned
    10 #define ll long long
    11 #define reg register
    12 #define F(i,a,b) for(i=a;i<=b;++i)
    13 using namespace std;
    14 bool e[MAXN+5][MAXN+5];
    15 int rad()
    16 {
    17     return rand()*rand();
    18 }
    19 int main()
    20 {
    21     freopen("data.in","w",stdout);
    22     srand(time(NULL));
    23     int n,m,w,k;
    24     n=rad()%MAXN+1; m=rad()%MAXN+1; w=rad()%min(MAXW,(n+1)*(m+1))+1; k=rad()%MAXK+1;
    25     printf("%d %d
    %d
    ",n,m,w);
    26     reg int i,a,b;
    27     F(i,1,w)
    28     {
    29         do{a=rad()%(n+1);b=rad()%(m+1);}while(e[a][b]);
    30         e[a][b]=1;
    31         printf("%d %d
    ",a,b);
    32     }
    33     printf("%d",k);
    34     return 0;    
    35 }
    数据生成
  • 相关阅读:
    字典树+二叉树
    ##22
    简单代码优雅写
    全排列
    【持续更新】哟!又在写BUG啊!
    大整数加法和大整数乘法
    【框架编程思想】线数筛的高级应用(欧拉12题和欧拉21题)
    【持续更新】 用算法流程实现的代码块们
    记忆化
    资源收集
  • 原文地址:https://www.cnblogs.com/hzoi-yzh/p/11131659.html
一二三 - 开发者的网上家园