Archived | 310-02-ACOJ-1873-限制数字
Archived | 310-02-ACOJ-1873-限制数字
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 为编号的区间的起点位置（代码中需要知道所以要存）
步骤：
- 读入 + 预处理数组（这非常好做）
- 读入限制条件 —> 对“大区间”进行处理把区间简化为尽量少项数的
- 下放约束条件：前面只对“大区间”进行了merge 现在要从大到小，对每个区间拆分为两个区间，两两merge 举个形象的例子：[3,6] 与[9,12] 这两个区间在并查集当中是合并的，但是[3,4],[9,10] 和[5,6],[11,12] 并没有被合并，这就是下放的意义，因为我们最后统计的是长度为1 的区间的并查集当中的个数
- 最后第一位的ans=9 ，然后从第二位开始遍历，求答案。
#include <iostream>
#include <cmath>
#define int long long
using namespace std;
const int maxn = 1e5 + 5;
const int P = 1e9 + 7;
// s[i]表示以i为编号的区间的起始位置, fa[i]表示i的并查集的父亲, f[i][j]是i为起点1<<j为长度的区间的编号
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 --)
// 判断这次的区间长度不会超过, 不然下一个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;
}这段代码值得注意：
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 ），所以必须要以这个逻辑来写。
下面为错误方法，请勿模仿（去掉了高亮）：
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;
}
本文作者：博主： gyrojeff 文章标题：Archived | 310-02-ACOJ-1873-限制数字
本文地址：https://cloud.tencent.com/developer/article/1827237
版权说明：若无注明，本文皆为“gyro永不抽风！”原创，转载请保留文章出处。
许可协议:署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 转载请保留原文链接及作者！
我的博客即将同步至腾讯云+社区，邀请大家一同入驻
腾讯云开发者
