Luogu2580 于是他错误的点名开始了 (Trie树)
2024-10-11 12:07:03
复习\(Trie\),忘了用\(val[]\)表示每个节点权值,用\(vis[]\)水过了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); a <= (c); ++ a)
#define nR(a,b,c) for(register int a = (b); a >= (c); -- a)
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Abs(a) ((a) < 0 ? -(a) : (a))
#define Swap(a,b) a^=b^=a^=b
#define ll long long
#define ON_DEBUG
#ifdef ON_DEBUG
#define D_e_Line printf("\n\n----------\n\n")
#define D_e(x) cout << #x << " = " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt","r",stdin);
#else
#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#endif
struct ios{
template<typename ATP>ios& operator >> (ATP &x){
x = 0; int f = 1; char c;
for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
x*= f;
return *this;
}
}io;
using namespace std;
#include <bitset>
int n;
char s[1007];
bitset<1007> vis[500007];
int trie[500007][26], trieIndex;
inline void Insert(char *str){
int rt = 0;
for(register int i = 0; str[i] != '\0'; ++i){
int v = str[i] - 'a';
if(!trie[rt][v]){
trie[rt][v] = ++trieIndex;
}
rt = trie[rt][v];
}
}
inline int Query(char *str){
int rt = 0, tot = 0;
for(register int i = 0; str[i] != '\0'; ++i){
int v = str[i] - 'a';
if(!trie[rt][v]){
return 0;
}
rt = trie[rt][v];
++tot;
}
if(vis[rt][tot]) return 2;
vis[rt][tot] = 1;
return 1;
}
int main(){
io>>n;
R(i,1,n){
scanf("%s", s);
Insert(s);
}
int Ques;
io >> Ques;
while(Ques--){
scanf("%s", s);
int ans = Query(s);
switch(ans){
case 0 :{
printf("WRONG\n");
break;
}
case 1 :{
printf("OK\n");
break;
}
case 2 :{
printf("REPEAT\n");
break;
}
}
}
return 0;
}
最新文章
- 深入理解DOM事件机制系列第四篇——事件模拟
- MySQL优化概述
- Windows C++ 子目录数量
- Redrain仿酷狗音乐播放器开发完毕,发布测试程序
- 位运算&;字节运算
- JDK中工具类的使用
- CTE在Oracle和Sqlserver中使用的差异
- Android(java)学习笔记225:Activity 4 种启动模式
- 使用python解数独
- sqlserver 电脑重启以后服务突然无法启动 报错
- 三十分钟学会 Less
- JQuery each遍历A标签获取href 和 里面指定的值
- 支持ajax跨域调用的WCF搭建示例
- UWP --- Display Content 显示基础内容
- applicationContext-common.xml]; nested exception is java.lang.NoClassDefFoundError: org/w3c/dom/ElementTraversal
- 第一天:html+JavaScript函数
- python_机器学习—sklearn_win_64-3.6安装&;&;测试
- 〖C语言〗C语言一个函数传递无限制多参数(不确定参数函数)的方法
- linux文本处理命令 一
- 组件prop检验