洛谷4305 [JLOI2011]不重复数字

  • 打个广告:$Blog$
  • 翻了所有的题解,发现竟然没有用$Trie$字典树做的,那我就来一发。
  • $Trie$字典树的复杂度对于这道题来说还行,刚好卡的过去,我只是提供一种思路,泥萌最好还是用哈希表。
  • 计算复杂度:
    • 数字长度$\leq 32$,数字总数$\leq 50000$,数据组数$\leq 50$
    • 最坏所有数字都不一样,一组数据共建树结点次数:$32 \times 50000 = 1600000 = 1.6 \times 10^6$。
    • $50$组数据:$1.6 \times 10^6 \times 50 = 8 \times 10^7$
  • 所以说可以刚刚好卡过了。
  • 算法:
    • 每读入一个数,就添加到字典树中,到最后一个结点发现不存在时,输出这个数;存在时,不输出这个数。以达到去重效果。
  • Code:
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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
inline int in(){
int X=0,w=0; char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}
struct node{
int son[10];
bool end;
}Trie[1600000];//这个大小上面算过了
int T,n,root,tot;
char num[50];
bool insert(char t[],int l){//添加数字到字典树中
int o=root;
for (int i=0;i<l;i++){
int ch=t[i]-'0';
if (!Trie[o].son[ch])
Trie[o].son[ch]=++tot;
o=Trie[o].son[ch];
}
if (Trie[o].end) return false;//判断字典树中是否存在这个数
Trie[o].end=true;
return true;
}
int main(){
T=in();
while (T--){
memset(&Trie,0,sizeof(Trie));//每次要清空一下,因为数组太大了,所以memset可能会很慢
tot=0;//但是还是能过,泥萌可以试一下每次只把1~tot的清空
n=in();
while (n--){
scanf("%s",num);
if (insert(num,strlen(num)))
printf("%s ",num);
}
printf("\n");
}
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×