109徐守佳

用户名：dotcpp0787174

访问量：110

签　名：

想AC的我戴上了WA面具

等　　级
排　　名	5660
经　　验	1485
参赛次数	0
文章发表	15
年　　龄	20
在职情况	学生
学　　校	内江师范学院
专　　业	柚子厨

　　自我简介：

TA的其他文章

[蓝桥杯2024年第十五届决赛真题-旋转九宫格] 测试数据量最大的一集
浏览：28

[信息学奥赛一本通T1547-区间和]-树状数组典型应用
浏览：11

[信息学奥赛一本通T1471-Phone List] Trie字典树做法
浏览：11

你可能喜欢

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

[信息学奥赛一本通T1471-Phone List] Trie字典树做法

　　作者: 109徐守佳　　　　发表时间：2024-09-18 01:20:58 浏览：11　|　评论：1　

原题链接：信息学奥赛一本通T1471-Phone List

# Trie tree:
[![](https://www.dotcpp.com/oj/ueditor/php/upload/image/20240513/1715564524958713.png)](https://www.dotcpp.com/oj/ueditor/php/upload/image/20240513/1715564524958713.png)
#AC代码
```cpp
#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N = 1e5 + 10,M = 2 * 1e4 + 10,inf = 0x3f3f3f3f;
int son[10*N][10],idx; //son-trie树,idx表示节点个数
bool st[N]; //每个单词结尾的节点标记
bool insert(char s[])					//插入字符串到trie树
{
    int len = strlen(s);
	int p=0;
	bool flag=false;
	for (int i=0;s[i];++i)
	{
		int u=s[i]-'0';
		if (!son[p][u])
		{
			son[p][u]=++idx;
		}
		else if (i==len-1)
		{
			flag=true;			
			return flag;
            //到结尾都没有插入任何新结点也说明有前缀,换个意思就是这个单词它走的所有路都被前面某个单词走过了(第一个单词插入的时候是不会进入这个条件的,因为它每一个字母都是新节点)
		}
		p=son[p][u];
		if (st[p])
		{
			flag=true;			//经过某个有标记(以这个节点结尾的标记)的结点说明有前缀
			return flag;
		}
	}
	st[p]=true;
	return flag;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while (T--)
    {
        memset(son,0,sizeof son); //每个测试数据都要清空trie树
        memset(st,0,sizeof st);
        idx = 0; //不要忘了重置节点数,RE了几次没看到
        int n;
        bool f = 0;
        char str[11];
        cin>>n;
        for(int i=0;i<n;i++)
        {  
            cin>>str;
            if(insert(str)) //如果成功找的前缀了,就是NO
            {
                f = 1;
            }
        }
        if(!f) puts("YES");
        else puts("NO");
    }
    return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

108叶先毅是个小蒟蒻

%%% orz
／￣￣￣￣￣￣￣￣￣
|　　可恶 还在卷吗？xsj！
＼
　￣￣∨￣￣￣￣￣￣
　 ∧＿∧
　(　・∀・)　 
　(　 つつヾ
　 | ｜ |　吧唧吧唧
　(＿_)＿)

2024-09-18 09:56:49

109徐守佳

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

[信息学奥赛一本通T1471-Phone List] Trie字典树做法

评论区

精彩推荐

川哥的吩咐（C++代码）

钟神赛车（C++代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C二级辅导-计负均正（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

【亲和数】（C语言代码）

C语言训练-求PI* （C语言代码）

109徐守佳

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

[信息学奥赛一本通T1471-Phone List] Trie字典树做法

评论区

精彩推荐

川哥的吩咐 （C++代码）

钟神赛车 （C++代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C二级辅导-计负均正 （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

【亲和数】 （C语言代码）

C语言训练-求PI* （C语言代码）

　　评论区

川哥的吩咐（C++代码）

钟神赛车（C++代码）

C二级辅导-计负均正（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

【亲和数】（C语言代码）