字典树求调
查看原帖
字典树求调
1121995
2021zjhs005楼主2024/3/7 16:52

rt,MLE #4 ~ # 10,WA Subtask 1。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define rrep(i,x,y) for(int i=x;i>=y;i--)
#define sc scanf
#define pr printf
inline int read(){int s=0,w=0;char c=getchar();while(!isdigit(c)){w |= (c=='-');c=getchar();}while(isdigit(c)){s=(s<<1)+(s<<3)+(c^48);c=getchar();}return w?-s:s;}

const int N=3e6+1;
int T,n,q,trie[N][65],cnt[N],idx;
string s;
map <string,bool> vis;

inline int calc(char x){
  if(x>='0'&&x<='9') return x-'0'+52;
  if(x>='a'&&x<='z') return x-'a'+26;
  return x-'A';
}

inline void insert(string s){
  int p=0,slen=s.size();
  rep(i,0,slen-1){
    int c=calc(s[i]);
    if(!trie[p][c]) trie[p][c]=++idx;
    p=trie[p][c];
    cnt[p]++;
  }
}

inline string find(string s){
  int p=0,slen=s.size();
  rep(i,0,slen-1){
    int c=calc(s[i]);
    if(!trie[p][c]) return "WRONG";
    p=trie[p][c];
  }
  if(cnt[p]) return "OK";
}

signed main(){
    n=read();
    idx=0;
    rep(i,1,n){
      cin>>s;
      insert(s);
    }
    q=read();
    while(q--){
      cin>>s;
      
      if(!vis[s]) cout<<find(s)<<endl;
      else pr("REPEAT\n");
      vis[s]=1;
      
    }
  return 0;
}
2024/3/7 16:52
加载中...