传送门
首先考虑暴力的做法，不要把注意力放在字串上面，考虑Sl1Sl1+1Sl1+2⋯Sr1==Sl2Sl2+1Sl2+2⋯Sr2的意义，就是 Sl1==Sl2 and Sl1+1==Sl2+1 and ⋯ and Sr1==Sr2
于是考虑并查集，把l1,l2和l1+1,l2+1⋯r1,r2连边，发现一个连通块里面的数字必须是一样的，于是每个连通块里面数字有10种选择，但是包含1的那个连通块不能为0，只有9种选择，设连通块个数是num，答案就是9×10num−1
这样时间复杂度O(n2α(n))，能够拿30pts
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]代表∀p∈[0,2i−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]如下图：
连完边以后还没有结束，我们现在还不能知道有多少连通块，于是我们要层层下推。
具体来说<i,f[i]>on f[j]⇒<i,f[i]>on f[j−1] and <i+2j−1,f[i]+2j−1>on f[j−1]
这个过程可以类比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(logn)级别，和线段树优化建图比较像，都是把多个重复的边压成一条，以优化时间/内存。
