• 周二. 11月 29th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[bzoj1227]虔诚的墓主人

admin

11月 28, 2021

题目描述

小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 }

数据生成

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注