题解 P4305 【[JLOI2011]不重复数字】
Snowflake_Pink
2019-03-05 23:26:19
- 打个广告：[$Blog$](https://www.17shou.vip/)
- 翻了所有的题解，发现竟然没有用$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：
```cpp
#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;
}
```