洛谷 2922 BZOJ 1590 [USACO08DEC]秘密消息Secret Message
2024-08-30 22:58:33
【题意概述】
给出n个01串组成的字典和m个询问,每次询问某个01串和多少个字典中的串有相同的前缀。(前缀长度是两串中较小的部分)
【题解】
直接上Trie树即可。树上每个节点记录两个信息:这个节点有多少个串经过,这个节点是多少个串的结尾。
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
#define rg register
#define N 500010
using namespace std;
int n,m,a[N][],now,ans,tot;
inline int read(){
int k=,f=; char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(''<=c&&c<='')k=k*+c-'',c=getchar();
return k*f;
}
int main(){
memset(a,,sizeof(a));
n=read(); m=read();
for(rg int i=;i<=n;i++){
int x=read(); now=;
while(x--){
int y=read();
if(a[now][y]>) now=a[now][y];
else a[now][y]=++tot,now=a[now][y];
a[now][]++;
}
a[now][]++;
}
while(m--){
int x=read(); bool ok=; ans=now=;
while(x--){
int y=read();
if(a[now][y]&&ok){
now=a[now][y];
if(a[now][]) ans+=a[now][];
}
else ok=;
}
if(ok) ans+=a[now][]-a[now][];
printf("%d\n",ans);
}
return ;
}
最新文章
- [游戏开发-学习笔记]菜鸟慢慢飞(四)-Camera
- poj-1017 Packets (贪心)
- oracle 回车、换行符
- uva 10474 Where is the Marble? 计数排序
- 【Stage3D学习笔记续】山寨Starling(十):高效游戏设计、纹理集和ATF
- Android-补间动画效果
- OC - 27.CATransition
- Python_生成測试数据
- 我喜欢的两个js类实现方式
- mysql浅龟定
- python迭代器以及itertools模块
- day01(计算机组成,进制,内存分布,操作系统)
- Win7 查看端口占用的进程,并根据进程id杀死进程。
- python note 12 生成器、推导式
- Nginx配置笔记
- 十、无事勿扰,有事通知(1)——NSNotification
- Intellij IDEA 设置启动JVM参数
- 内存池技术(UVa 122 Tree on the level)
- html使用技巧
- 【学习笔记】FreeMarker 之于Servlet与Stuts2的应用
热门文章
- POJ2127 Greatest Common Increasing Subsequence
- Win7 64 位 vs2012 pthread 配置
- 33. Extjs中的tree节点的操作
- 【146】ArcObjects类库索引
- CodeForces 731C Socks (DFS或并查集)
- bzoj 2101: [Usaco2010 Dec]Treasure Chest 藏宝箱【区间dp】
- [Qt及Qt Quick开发实战精解] 第1章 多文档编辑器
- svn报错:Cannot negotiate authentication mechanism
- php 页面展示
- js jquery 获取服务器控件的三种方法