310-02-ACOJ-1873-限制数字
题目描述：
一个长度为n的大数，用$S_1,..S_n$表示，其中$S_i$表示数的第i位，$S_1$是数的最高位。
现告诉你一些限制条件，每个条件表示为四个数，$l_1,r_1,l_2,r_2$，即两个长度相同的区间，表示子串$S_{l_1} … S_{r_1}$与$S_{l_2} … S_{r_2}$完全相同。
给定限制条件后，问满足以上所有条件的数有多少个。
题解：
首先考虑没有限制的情况是怎么样的，在没有限制的情况之下，所有的可能的情况应该是第一位数字有九种可能性（不可以是0），其余的各位都有十种可能性，将每位的种数相乘（小学问题）
而现在加上了限制条件，无非就是某几位的可能型变得一样了。
这个时候我们就可以使用并查集，如果某两个数字应该是相同的，那么就合并，最后的答案应该就是并查集的个数的$10$连乘（这里没有考虑首位为$9$的情况，这在后文会考虑到）。
但是很遗憾，单独直接使用并查集肯定会超时，时间复杂度为$O(n^2)$。而解决这一问题的方法就是使用二进制优化这一手段。
这里还是使用倍增的思想，我们可以对并查集的每个组编号。而且并查集的储存方式也要进行改变。
定义：
$f[i][j]$是起点为$i$区间$2^j$，即$1<<j$的区间
$fa[i]$表示第$i$个区间的父亲（并查集所需要的数组）
$s[i]$表示以$i$为编号的区间的起点位置（代码中需要知道所以要存）
步骤：
读入 + 预处理数组（这非常好做）
读入限制条件 —> 对“大区间”进行处理把区间简化为尽量少项数的$2^i$之和
下放约束条件：前面只对“大区间”进行了$merge$
现在要从大到小，对每个区间拆分为两个区间，两两$merge$
举个形象的例子：$[3,6]$与$[9,12]$这两个区间在并查集当中是合并的，但是$[3,4],[9,10]$和$[5,6],[11,12]$并没有被合并，这就是下放的意义，因为我们最后统计的是长度为$1$的区间的并查集当中的个数
最后第一位的$ans=9$，然后从第二位开始遍历，求答案。
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
| #include <iostream>
#include <cmath>
#define int long long
using namespace std;
const int maxn = 1e5 + 5;
const int P = 1e9 + 7;
int f[maxn][25], fa[maxn * 25], s[maxn * 25];
int n, m, cnt;
void pre_work() {
for (int j = 0; j <= log2(n) + 1; j ++)
for (int i = 1; i <= n; i ++) {
f[i][j] = ++ cnt;
fa[cnt] = cnt;
s[cnt] = i;
}
}
int get(int x) {
if (x == fa[x]) return x;
else return fa[x] = get(fa[x]);
}
void merge(int x, int y, int k) {
int p = get(f[x][k]), q = get(f[y][k]);
if (p > q) swap(p, q);
fa[q] = p;
}
signed main() {
cin >> n >> m;
pre_work();
for (int i = 1; i <= m; i ++) {
int l1, l2, r1, r2; cin >> l1 >> r1 >> l2 >> r2;
for (int k = log2(r1 - l1 + 1); k >= 0; k --)
if (l1 + (1 << k) - 1 <= r1) {
merge(l1, l2, k);
l1 += (1 << k); l2 += (1 << k);
}
}
int tmp, tmps;
for (int k = log2(n) + 1; k; k --)
for (int i = 1; i + (1 << k) - 1 <= n; i ++) {
tmp = get(f[i][k]); tmps = s[tmp];
merge(i, tmps, k - 1); merge(i + (1 << (k - 1)), tmps + (1 << (k - 1)), k - 1);
}
int ans = 9;
for (int i = 2; i <= n; i ++)
if (fa[f[i][0]] == f[i][0])
ans = (ans * 10) % P;
cout << ans << endl;
return 0;
}
|
这段代码值得注意：
1
2
3
4
5
| void merge(int x, int y, int k) {
int p = get(f[x][k]), q = get(f[y][k]);
if (p > q) swap(p, q);
fa[q] = p;
}
|
由于$k$是一样的，所以区间序号上，$p,q$“同阶”，就意味着$x<y\rightarrow p<q;~x=y \rightarrow p=q;~x > y \rightarrow p > q$
在合并区间的过程中，为了保证父亲区间永远在前面（因为先统计了第一位的$9$），所以必须要以这个逻辑来写。
下面为错误方法，请勿模仿（去掉了高亮）：
1
2
3
4
5
| void merge(int x, int y, int k) {
int p = get(f[x][k]), q = get(f[y][k]);
if (p < q) fa[q] = p;
else fa[p] = q;
}
|
