求职trie hack数据挂了
查看原帖
求职trie hack数据挂了
704275
无名之雾楼主2024/3/29 20:20

rt.

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
inline void write(int x){ 
    if(x==0){putchar('0');return;}
	int len=0,k1=x,c[10005];
	if(k1<0)k1=-k1,putchar('-');
	while(k1)c[len++]=k1%10+'0',k1/=10;
	while(len--)putchar(c[len]);
}
const int N=1e6+5;
struct node{
	bool repeat;
	int son[26],num;
}trie[N]; 
int cnt=1;
void insert(string s){
	int now=0;
	for(int i=0;i<s.size();i++){
		int ch=s[i]-'a';
		if(trie[now].son[ch]==0)trie[now].son[ch]=cnt++;
		now=trie[now].son[ch];
		trie[now].num++;
	}
}
int find(string s){
	int now=0;
	for(int i=0;i<s.size();i++){
		int ch=s[i]-'a';
		if(trie[now].son[ch]==0)return 3;
		now=trie[now].son[ch];
	}
	if(trie[now].num==0)return 3;
	if(!trie[now].repeat){
		trie[now].repeat=1;
		return 1;
	}
	return 2;
}
signed main(){
	int n=read();
	string s;
	for(int i=1;i<=n;i++){
		cin>>s;
		insert(s);
	}
	int m=read();
	while(m--){
		cin>>s;
		int r=find(s);
		if(r==1)puts("OK");
		else if(r==2)puts("REPEAT");
		else puts("WRONG");
	}
	return 0;
}
2024/3/29 20:20
加载中...