「codevs1998」终极武器 - 数位trie树 | Bill Yang's Blog

「codevs1998」终极武器 - 数位trie树

题目大意

经过一番周折,精英队伍的队员们终于来到了关押applepi的牢狱面前。心中神一般的领袖applepi就在眼前,队员们都不由自主地跪烂膝盖……不过令他们沮丧的是,牢狱的大锁没有钥匙孔,黑魔法师Vani根本就没有指望它再被打开。幸好队员们携带了新研制的终极武器——k型氙激光器(Xenon Laser - k,代号XLk),可以用来破拆这把锁。不过作为一道终极武器,它的启用规则异常严格。
Xenon Laser - k上共有$N$个波段能够发射激光,每个波段可以用一个闭区间$[a_i,b_i]$来表示,其中$a_i,b_i$为正整数,$b_i-1<a_i<=b_i$。对于两个数字$p$和$q$,如果对于这$N$个波段内的任意一个整数$num$,把它在十进制表示下的后$K$位中某一位上$p$的换成$q$(或者$q$换成$p$),都满足得到的整数仍然在这$N$个波段内,那么称在该激光器中,数字$p$和$q$是等价的。我们称两两之间$k$等价的数字组成一个等价类。
激光器附带了$9$个发射匣,代表$1\rightarrow 9$这$9$个数字。只有把同一个等价类的数字对应的发射匣安置在一排上,Xenon Laser - k才能够启动。给定$N$个波段,现在就请你求出$1\rightarrow 9$这$9$个数字分成了哪些等价类,并且每行输出一个等价类。
本题描述比较抽象,请参考样例解释。


题目分析

本题可以用一个非常麻烦的模拟解决。
然而我们(我、achen、KEKE_046)都不会写模拟,因此我们选择使用$trie$树。

根据题目给出的上下界将各个位拆分建成$trie$树,因为建立$trie$树的过程类似数位动规,因此称为数位$trie$树。

判断两个数字是否是在同一个等价类中的方法是:它们的后$K$位构成的树完全相同。
我们可以在$trie$树上递归到后$K$位然后判断其子树是否完全相同,具体可以使用$Hash$实现。

最后输出答案用并查集维护一下即可。


代码

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const LL mod=1e9+7;
const int maxn=5000005;
int n,k;
struct Trie {
int root,cnt;
int child[maxn][10];
int f[maxn],tmp1[21],tmp2[21];
LL Hash[maxn];
Trie() {
cnt=0;
root=++cnt;
}
int Get_Hash(int depth) {
if(!depth)return 0;
if(f[depth])return f[depth];
for(int i=0; i<=9; i++)f[depth]=((LL)f[depth]*131+i+Get_Hash(depth-1))%mod;
return f[depth];
}
void build(int Now,bool Up,bool Down,int pos) {
if(pos==0)return;
if(!Up&&!Down) {
Hash[Now]=Get_Hash(pos);
return;
}
int up=Up?tmp2[pos]:9,down=Down?tmp1[pos]:0;
for(int i=down; i<=up; i++) {
if(!child[Now][i])child[Now][i]=++cnt;
build(child[Now][i],Up&&i==up,Down&&i==down,pos-1);
}
}
void insert(LL Left,LL Right) {
for(int i=1; i<=19; i++)tmp1[i]=Left%10,Left/=10;
for(int i=1; i<=19; i++)tmp2[i]=Right%10,Right/=10;
build(root,1,1,19);
}
void dfs(int Now) {
for(int i=0; i<=9; i++) {
int Next=child[Now][i];
if(!Next)continue;
dfs(Next);
Hash[Now]=((LL)Hash[Now]*131+Hash[Next]+i)%mod;
}
}
bool check(int Now,int x,int y,int pos) {
if(pos<=k&&((!child[Now][x])^(!child[Now][y])))return false;
if(pos<=k&&child[Now][x]&&child[Now][y]&&Hash[child[Now][x]]!=Hash[child[Now][y]])return false;
for(int i=0; i<=9; i++)
if(child[Now][i]&&!check(child[Now][i],x,y,pos-1))return false;
return true;
}
} trie;
vector<int>ans[10];
int father[15];
int Get_Father(int x) {
if(father[x]==x)return x;
return father[x]=Get_Father(father[x]);
}
int main() {
n=Get_Int();
k=Get_Int();
for(int i=1; i<=n; i++) {
LL x=Get_Int(),y=Get_Int();
trie.insert(x,y);
}
trie.dfs(1);
for(int i=1; i<=9; i++)father[i]=i;
for(int i=1; i<=9; i++)
for(int j=i+1; j<=9; j++)
if(trie.check(1,i,j,19))father[Get_Father(j)]=Get_Father(i);
for(int i=1; i<=9; i++)ans[Get_Father(i)].push_back(i);
for(int i=1; i<=9; i++) {
if(!ans[i].size())continue;
for(int x:ans[i])printf("%d",x);
putchar('\n');
}
return 0;
}
本篇文章有用吗?有用还不快点击!
0%