Steven_MengのBlog


传送门

首先考虑暴力的做法,不要把注意力放在字串上面,考虑$S_{l_1}S_{l_1+1}S_{l_1+2} \cdots S_{r_1} == S_{l_2}S_{l_2+1}S_{l_2+2} \cdots S_{r_2}$的意义,就是$S_{l_1}==S_{l_2} \text{&&} S_{l_1 +1} == S_{l_2+1} \text{&&} \cdots \text{&&} S_{r_1}==S_{r_2}$

于是考虑并查集,把$l_1,l_2$和$l_1+1,l_2+1 \cdots$$r_1,r_2$连边,发现一个连通块里面的数字必须是一样的,于是每个连通块里面数字有$10$种选择,但是包含$1$的那个连通块不能为$0$,只有$9$种选择,设连通块个数是$num$,答案就是$9 \times 10^{num-1}$

这样时间复杂度$O(n^2 \alpha(n))$,能够拿$30 pts$

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
41
42
43
44
#include <bits/stdc++.h>
#define MAXN 100005
#define MOD 1000000007
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
namespace BCJ{
int fa[MAXN];
inline void Init(){
for (register int i=0;i<MAXN;++i) fa[i]=i;
}
inline int Find(int x){
return fa[x]==x?x:fa[x]=Find(fa[x]);
}
}
using namespace BCJ;
int main(){
int n=read(),m=read();
Init();
for (register int i=1;i<=m;++i){
int l1=read(),r1=read(),l2=read(),r2=read();
for (register int j=l1;j<=r1;++j){
fa[Find(j)]=Find(j-l1+l2);
}
}
int ans=0;
for (register int i=1;i<=n;++i){
if (fa[i]==i) ans++;
}
long long ret=9;
for (register int i=1;i<=ans-1;++i) ret=(ret*10)%MOD;
printf("%d\n",ret);
}

考虑如何优化,肯定是在刚才的并查集上面优化,不妨考虑以空间换时间,我们创建一个二维的并查集数组$f[][]$,其中$f[i][j]$代表$\forall p \in [0,2^i-1] , (j+p)和(f[i][j]+p)$之间都有边相连。

考虑如何连边,这个类似于二进制拆分。

1
2
3
4
5
6
7
for (register int j=LOG-1;j>=0;--j){
int d=(1<<j);
if (l1+d-1<=r1){
Merge(l1,l2,j);
l1+=d,l2+=d;
}
}

比方说我们连边$[1,3],[5,7]$如下图:

连完边以后还没有结束,我们现在还不能知道有多少连通块,于是我们要层层下推。

具体来说$ \text{on } f[j] \Rightarrow \text{on } f[j-1] \text{ && } \text{on } f[j-1]$

这个过程可以类比$\rm ST$表初始化:

1
ST[i][j]=max(ST[i-1][j],ST[i-1][j+(1<<(i-1))]);

处理完之后,$f[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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
#define MAXN 100005
#define LOG 25
#define MOD 1000000007
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
namespace BCJ{
int f[LOG][MAXN];
inline void Init(int n){
for (register int i=1;i<=n;++i){
for (register int j=0;j<LOG;++j){
f[j][i]=i;
}
}
}
inline int Find(int *fa,int x){
return fa[x]==x?x:fa[x]=Find(fa,fa[x]);
}
inline void Merge(int x,int y,int lev){
int fax=Find(f[lev],x),fay=Find(f[lev],y);
if (fax!=fay) f[lev][f[lev][fax]]=f[lev][fay];
}
}
using namespace BCJ;
int main(){
int n=read(),m=read();
Init(n);
for (register int i=1;i<=m;++i){
int l1=read(),r1=read(),l2=read(),r2=read();
for (register int j=LOG-1;j>=0;--j){
int d=(1<<j);
if (l1+d-1<=r1){
Merge(l1,l2,j);
l1+=d,l2+=d;
}
}
}
for (register int j=LOG-1;j>=1;--j){
int d=(1<<j);
for (register int i=1;i+d-1<=n;++i){
int fa=Find(f[j],i);
Merge(i,fa,j-1);
Merge(i+(d>>1),fa+(d>>1),j-1);
}
}
int ans=0;
for (register int i=1;i<=n;++i) ans+=(Find(f[0],i)==i);
long long ret=9;
for (register int i=1;i<=ans-1;++i) ret=(ret*10)%MOD;
printf("%d\n",ret);
}

总结:这道题将多次重复的加边操作通过倍增优化到$O(\log n)$级别,和线段树优化建图比较像,都是把多个重复的边压成一条,以优化时间/内存。

 评论