当前位置:网站首页>信息学奥赛一本通 1337:【例3-2】单词查找树 | 洛谷 P5755 [NOI2000] 单词查找树
信息学奥赛一本通 1337:【例3-2】单词查找树 | 洛谷 P5755 [NOI2000] 单词查找树
2022-07-05 20:10:00 【君义_noip】
【题目链接】
ybt 1337:【例3-2】单词查找树
洛谷 P5755 [NOI2000] 单词查找树
【题目考点】
1. 字典树
【解题思路】
解法1:字典树
字典树模板题。学习字典树相关知识请在csdn搜“字典树”或“tire树”。
该题说文件总长度不超过32K, 32 K B = 32 ∗ 1024 B = 32768 B 32KB = 32*1024B = 32768B 32KB=32∗1024B=32768B,总字符个数不会超过33000个。因此结点池总数量设为33000。
【题解代码】
解法1:字典树
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int child[26];//child[i]:字符是i+'A'的孩子结点的地址
};
Node node[33000];
int p, root;//根结点root地址为0,从地址1开始分配结点
void insert(string s)//向字典树插入单词s
{
int pf = root;//当前关注的结点的地址
for(int i = 0; i < s.length(); ++i)
{
if(node[pf].child[s[i]-'A'] == 0)
node[pf].child[s[i]-'A'] = ++p;//分配新结点
pf = node[pf].child[s[i]-'A'];//pf指向下一个结点
}
}
int getNodeNum(int r)//获取根结点地址为r的树的结点数
{
int sum = 1;//自己就是1个结点
for(int i = 0; i < 26; ++i)//统计r子树结点数量
{
if(node[r].child[i] > 0)
sum += getNodeNum(node[r].child[i]);
}
return sum;
}
int main()
{
string s;
while(cin >> s)
insert(s);//将单词s插入字典树
cout << getNodeNum(root);//获取整棵树的结点数
return 0;
}
边栏推荐
- JS implementation prohibits web page zooming (ctrl+ mouse, +, - zooming effective pro test)
- Leetcode skimming: binary tree 10 (number of nodes of a complete binary tree)
- 浅浅的谈一下ThreadLocalInsecureRandom
- ffplay文档[通俗易懂]
- c语言oj得pe,ACM入门之OJ~
- Let's talk about threadlocalinsecurerandom
- Notes on key vocabulary in the English original of the biography of jobs (12) [chapter ten & eleven]
- 淺淺的談一下ThreadLocalInsecureRandom
- 618 "low key" curtain call, how can baiqiushangmei join hands with the brand to cross the "uncertain era"?
- [C language] three implementations of quick sorting and optimization details
猜你喜欢
kubernetes资源对象介绍及常用命令(五)-(ConfigMap&Secret)
Database logic processing function
解决Thinkphp框架应用目录下数据库配置信息修改后依然按默认方式连接
秋招字节面试官问你还有什么问题?其实你已经踩雷了
【数字IC验证快速入门】3、数字IC设计全流程介绍
leetcode刷题:二叉树18(最大二叉树)
CADD课程学习(7)-- 模拟靶点和小分子相互作用 (半柔性对接 AutoDock)
618 "low key" curtain call, how can baiqiushangmei join hands with the brand to cross the "uncertain era"?
Scala基础【HelloWorld代码解析,变量和标识符】
计算lnx的一种方式
随机推荐
CCPC 2021威海 - G. Shinyruo and KFC(组合数,小技巧)
Securerandom things | true and false random numbers
nprogress插件 进度条
A solution to PHP's inability to convert strings into JSON
零道云新UI设计中
Fundamentals of deep learning convolutional neural network (CNN)
解决php无法将string转换为json的办法
深度学习 卷积神经网络(CNN)基础
1: Citation;
E. Singhal and Numbers(质因数分解)
解决Thinkphp框架应用目录下数据库配置信息修改后依然按默认方式连接
Leetcode brush questions: binary tree 18 (largest binary tree)
- Oui. Net Distributed Transaction and Landing Solution
[quick start of Digital IC Verification] 3. Introduction to the whole process of Digital IC Design
Multi branch structure
Win10 x64环境下基于VS2017和cmake-gui配置使用zxing以及opencv,并实现data metrix码的简单检测
Unity编辑器扩展 UI控件篇
【c语言】快速排序的三种实现以及优化细节
Leetcode skimming: binary tree 16 (path sum)
【数字IC验证快速入门】8、数字IC中的典型电路及其对应的Verilog描述方法