HDU 5116 Everlasting L

HDU 5116 Everlasting L

题目链接：HDU-5116

题意:给定若干个整数点，若一个点集满足P = {(x, y), (x + 1, y), . . . , (x + a, y), (x, y + 1), . . . , (x, y + b)}(a, b ≥ 1)  且 gcd(a, b)==1 则称这是一个好(a, b)-L集。求共有多少个(A, B)满足A，B都是好L集且A，B不相交。

思路是先找出好L集的数量a，再找出相交的好L集对数b，则答案为a * a - b 。

首先要解决的第一个问题是求出a，一个自然的思路是对于每个点，分别向右、向下搜索，但是这样做会超时。所以我们需要优化一下。

首先算出每个点向右、向下最远长度，记为rght[i][j]和down[i][j]。然后对于每个点，在向右搜索时，对于当前搜索到的长度L，我们希望能知道有多少向下的长度D可以与之组成一个好L-集。所以优化的思路就是处理出在[ 1, down[i][j] ]范围内，有多少数与L互质。我们用f[i][j]表示在[0, j]范围内有多少数与i的gcd等于1。

这样我们就解决了第一个问题。

对于第二个问题，我们处理出，对于每一个点(i, j)，有多少好L-集的下路经过点(i, j)，用sum[i][j]表示，那么假设存在x个右路经过点(i, j)的好L-集，则 b += 2 * x * sum[i][j]。

具体请参照代码：

 1 //f[i][j]表示在[1,j]范围内，有多少数与i的gcd=1。
 2 //g[i][j]表示在sum(gcd(a,b)==1) (1<=a<=i && 1<=b<=j)
 3 //rght[i][j]表示点(i, j)右路最长长度
 4 //down[i][j]表示点(i, j)下路最长长度
 5 //sum[i][j]表示下路通过(i, j)的好L-集的个数
 6 
 7 #include<cstdio>
 8 #include<set>
 9 #include<map>
10 #include<cstring>
11 #include<algorithm>
12 #include<queue>
13 #include<iostream>
14 using namespace std;
15 typedef long long LL;
16 
17 const LL MAXN=210;
18 
19 LL gcd(LL a,LL b)
20 {
21     if(b==0) return a;
22     return gcd(b,a%b);
23 }
24 bool vis[MAXN][MAXN];
25 LL g[MAXN][MAXN],f[MAXN][MAXN],down[MAXN][MAXN],rght[MAXN][MAXN],sum[MAXN][MAXN];
26 int main()
27 {
28 #ifdef LOCAL
29     freopen(&#","r",stdin);
30 #endif
31     memset(g,0,sizeof(g));
32     memset(f,0,sizeof(f));
33     for(LL i=1;i<=200;i++)
34         for(LL j=1;j<=200;j++)
35         {
36             f[i][j]=f[i][j-1]+(gcd(i,j)==1);
37             g[i][j]=g[i-1][j]+f[i][j];
38         }
39     LL T;
40     scanf("%lld",&T);
41     for(LL tt=1;tt<=T;tt++)
42     {
43         memset(down,0,sizeof(down));
44         memset(rght,0,sizeof(rght));
45         memset(vis,0,sizeof(vis));
46         memset(sum,0,sizeof(sum));
47         LL n;
48         scanf("%lld",&n);
49         for(LL i=1;i<=n;i++)
50         {
51             LL x,y;
52             scanf("%lld%lld",&x,&y);
53             vis[x][y]=1;
54         }
55         for(LL i=200;i>=1;i--)
56             for(LL j=200;j>=1;j--)
57                 if(vis[i][j])
58                 {
59                     if(vis[i+1][j]) down[i][j]=down[i+1][j]+1;
60                     if(vis[i][j+1]) rght[i][j]=rght[i][j+1]+1;
61                 }
62         LL a=0;
63         memset(sum,0,sizeof(sum));
64         for(LL i=1;i<=200;i++)
65             for(LL j=1;j<=200;j++)
66                 if(vis[i][j])
67                 {
68                     LL cnt[MAXN];
69                     memset(cnt,0,sizeof(cnt));
70                     for(LL k=1;k<=down[i][j];k++)
71                         cnt[k]+=f[k][rght[i][j]];
72                     for(LL k=down[i][j]-1;k>=0;k--)
73                         cnt[k]+=cnt[k+1];
74                     for(LL k=0;k<=down[i][j];k++)
75                         sum[i+k][j]+=cnt[k];
76                     a+=cnt[0];
77                 }
78         LL b=0;
79         for(LL i=1;i<=200;i++)
80             for(LL j=1;j<=200;j++)
81                 if(vis[i][j])
82                 {
83                     LL cnt=0;
84                     for(LL k=rght[i][j];k>=0;k--)
85                     {
86                         cnt+=f[k][down[i][j]];
87                         b+=2*cnt*sum[i][j+k];
88                     }
89                     b-=g[down[i][j]][rght[i][j]]*g[down[i][j]][rght[i][j]];
90                 }
91         printf("Case #%lld: %lldn",tt,a*a-b);
92     }
93     return 0;
94 }

转载于:.html