当前位置:网站首页>Informatics Olympiad 1337: [example 3-2] word search tree | Luogu p5755 [noi2000] word search tree
Informatics Olympiad 1337: [example 3-2] word search tree | Luogu p5755 [noi2000] word search tree
2022-07-05 20:17:00 【Jun Yi_ noip】
【 Topic link 】
ybt 1337:【 example 3-2】 Word search tree
Luogu P5755 [NOI2000] Word search tree
【 Topic test site 】
1. Dictionary tree
【 Their thinking 】
solution 1: Dictionary tree
Dictionary tree template questions . Learn about dictionary tree in csdn search “ Dictionary tree ” or “tire Trees ”.
This question says that the total length of the document does not exceed 32K, 32 K B = 32 ∗ 1024 B = 32768 B 32KB = 32*1024B = 32768B 32KB=32∗1024B=32768B, The total number of characters will not exceed 33000 individual . Therefore, the total number of node pools is set to 33000.
【 Solution code 】
solution 1: Dictionary tree
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int child[26];//child[i]: Character is a i+'A' The address of the child node
};
Node node[33000];
int p, root;// Root node root The address is 0, From address 1 Start assigning nodes
void insert(string s)// Insert words into the dictionary tree s
{
int pf = root;// The address of the currently concerned node
for(int i = 0; i < s.length(); ++i)
{
if(node[pf].child[s[i]-'A'] == 0)
node[pf].child[s[i]-'A'] = ++p;// Assign new nodes
pf = node[pf].child[s[i]-'A'];//pf Point to the next node
}
}
int getNodeNum(int r)// Get the root node address as r Node number of the tree of
{
int sum = 1;// I am 1 Nodes
for(int i = 0; i < 26; ++i)// Statistics r Number of subtree nodes
{
if(node[r].child[i] > 0)
sum += getNodeNum(node[r].child[i]);
}
return sum;
}
int main()
{
string s;
while(cin >> s)
insert(s);// Put the word s Insert dictionary tree
cout << getNodeNum(root);// Get the node number of the whole tree
return 0;
}
边栏推荐
- 基金网上开户安全吗?去哪里开,可以拿到低佣金?
- Elk distributed log analysis system deployment (Huawei cloud)
- 银河证券在网上开户安全吗?
- 19 Mongoose模块化
- model方法
- CTF逆向基础
- [quick start of Digital IC Verification] 3. Introduction to the whole process of Digital IC Design
- selenium 元素信息
- 14. Users, groups, and permissions (14)
- 2022年7月4日-2022年7月10日(ue4视频教程mysql)
猜你喜欢
2023年深圳市绿色低碳产业扶持计划申报指南
【数字IC验证快速入门】3、数字IC设计全流程介绍
leetcode刷题:二叉树15(找树左下角的值)
Parler de threadlocal insecurerandom
Convolution free backbone network: Pyramid transformer to improve the accuracy of target detection / segmentation and other tasks (with source code)
零道云新UI设计中
CVPR 2022 | 常见3D损坏和数据增强
Enter the parallel world
无卷积骨干网络:金字塔Transformer,提升目标检测/分割等任务精度(附源代码)...
JS implementation prohibits web page zooming (ctrl+ mouse, +, - zooming effective pro test)
随机推荐
IC科普文:ECO的那些事儿
Flume series: interceptor filtering data
sun. misc. Base64encoder error reporting solution [easy to understand]
Convolution free backbone network: Pyramid transformer to improve the accuracy of target detection / segmentation and other tasks (with source code)
Leetcode skimming: binary tree 16 (path sum)
618 "low key" curtain call, how can baiqiushangmei join hands with the brand to cross the "uncertain era"?
leetcode刷题:二叉树17(从中序与后序遍历序列构造二叉树)
y57.第三章 Kubernetes从入门到精通 -- 业务镜像版本升级及回滚(三十)
How to choose a good external disk platform, safe and formal?
DP:树DP
c语言oj得pe,ACM入门之OJ~
基金网上开户安全吗?去哪里开,可以拿到低佣金?
[quick start of Digital IC Verification] 6. Quick start of questasim (taking the design and verification of full adder as an example)
Go language learning tutorial (XV)
Ffplay document [easy to understand]
mongodb基操的练习
Leetcode: binary tree 15 (find the value in the lower left corner of the tree)
Jvmrandom cannot set seeds | problem tracing | source code tracing
leetcode刷题:二叉树11(平衡二叉树)
ICTCLAS word Lucene 4.9 binding