【洛谷 P1666】 前缀单词 (Trie)
2024-09-04 13:08:01
考试时暴搜50分。。。其实看到“单词”,“前缀”这种字眼时就要想到\(Trie\)的,哎,我太蒻了。
以一个虚点为根,建一棵\(Trie\),然后\(dfs\),
以当前点为根的答案就是\(Ans_u=(\prod_{\text{v是u的子树}}Ans_v)+\text{有单词以这个点结尾 ? 1 : 0}\),乘法原理嘛,如果有单词在这里结尾,那么就多一种情况:选这个单词且不选所有子树。
答案就是\(Ans_{\text{根}}\)
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
#define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);
#define Close fclose(stdin);fclose(stdout);
int n;
char a[60];
struct Trie{
Trie *son[27];
int p;
}*root = new Trie();
inline void Insert(){
int len = strlen(a + 1);
Trie *now = root;
for(int i = 1; i <= len; ++i){
if(now->son[a[i] - 'a'] == NULL)
now->son[a[i] - 'a'] = new Trie(), now->son[a[i] - 'a']->p = 0;
now = now->son[a[i] - 'a'];
}
now->p = 1;
}
long long dp(Trie *now){
long long sum = 1;
for(int i = 0; i < 26; ++i)
if(now->son[i] != NULL){
sum *= dp(now->son[i]);
}
return sum + now->p;
}
int main(){
Open("prefix");
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%s", a + 1), Insert();
printf("%lld\n", dp(root));
return 0;
}
最新文章
- MySQL数据库出现The server quit without updating PID file.
- Android开发之补间动画、XML方式定义补间动画
- ArcGIS API for Silverlight 之ElementLayer使用及TextSymbol的模板使用
- 用HTML5实现的各种排序算法的动画比较 及算法小结
- timus 1033 Labyrinth(BFS)
- CentOS 7 安装 tomcat7.0
- VB-获取本机计算机名,登录名、ip地址
- Makefile与shell脚本区别
- 设置session存储在int sqlserver上---使用aspnet_regsql.exe工具
- 插件开发之360 DroidPlugin源码分析(一)初识
- 使用 Nginx 为 Linux 实例绑定多个域名
- Docker(十三)-Docker save and load镜像保存
- ROM、PROM、EPROM、EEPROM、FLASH ROM、FLASH、eMMC
- tf之变量与作用域
- 《Photoshop智能手机APP界面设计》学习笔记-转
- (原创)一个简洁通用的调用DLL函数的帮助类
- spring json的支持
- imperva-指定url禁止访问
- hdoj 1753 大明A+B 高精度/java
- Python pycharm(windows版本)部署spark环境
热门文章
- Memcached Hash算法
- 【page.js】配置及Page函数说明
- 关于缺失值(missing value)的处理---机器学习 Imputer
- Android Service 服务(三)—— bindService与remoteService
- linux中升级安装python2.7
- ios UI自动化测试学习笔记
- chm文件空白如何解决
- vue2.0中动画
- Thread.currentThread().getContextClassLoader().loadClass(className)和Class.forName(className)的区别
- js获取上传文件内容