洛谷 P2580 于是他错误的点名开始了 题解

每日一题 day10 打卡

Analysis

trie树模板题，只需用到简单的插入和查询就好了

如果想要学trie树，见信息学奥赛一本通·提高篇P82

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int n,m,cnt=;

 string a[];

 int ch[][];

 bool bo[],book[];

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';

     if(f) return x;

     return -x;

 }

 void insert(string x)

 {

     int len=x.size();

     int u=;

     for(int i=;i<len;i++)

     {

         int c=x[i]-'a';

         if(ch[u][c]==)ch[u][c]=++cnt;

         u=ch[u][c];

     }

     bo[u]=true;

 }

 int check(string y)

 {

     int len=y.size();

     int u=;

     for(int i=;i<len;i++)

     {

         int c=y[i]-'a';

         if(ch[u][c]==)return ;

         u=ch[u][c];

     }

     if(bo[u]!=true)return ;

     else if(bo[u]==true&&book[u]==)

     {

         book[u]=;

         return ;

     }

     else if(bo[u]==true&&book[u]==)

     {

         return ;

     }

 }

 int main()

 {

     n=read();

     for(int i=;i<=n;i++)

     {

         cin>>a[i];

         insert(a[i]);

     }

     m=read();

     string x;

     for(int i=;i<=m;i++)

     {

         cin>>x;

         int se=check(x);

         if(se==)cout<<"OK"<<endl;

         if(se==)cout<<"WRONG"<<endl;

         if(se==)cout<<"REPEAT"<<endl;

     }

     return ;

 }

请各位大佬斧正