求助Trie树板子题
查看原帖
求助Trie树板子题
294736
bovine__kebi楼主2020/5/26 10:39

RT,没过样例,求帮看看为什么

#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#include<bits/stdc++.h>
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21], *p1 = buf, *p2 = buf;
using namespace std;
const int maxn=1e4+5;
typedef long long ll;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
inline void print(int x)
{
     if(x<0) putchar('-'),x=-x;
     if(x>9) print(x/10);
     putchar(x%10+'0');
}
int trie[maxn][11];bool vis[maxn];int ch[maxn][11];
int cnt=1;
void add(char *s)
{
	int n=strlen(s);
	int u=1;
	for(int i=0;i<n;i++)
	{
		int c=s[i]-'0';
		if(!trie[u][c])
		{
			ch[u][c]=++cnt;
		}
		u=ch[u][c];
	}
	vis[u]=true;
}
bool find(char *s)
{
    int len=strlen(s);
    int u=1;
    for(int i=0;i<len;i++)
    {
        int c=s[i]-'0';
        if(!trie[u][c])
            return vis[u];
        u=ch[u][c];
    }
    return true;
}
int main()
{
	int T;
	T=read();
	for(int i=1;i<=T;i++)
	{
	    memset(trie,0,sizeof(trie));
	    memset(ch,0,sizeof(ch));
	    memset(vis,0,sizeof(vis));
	    int n;n=read();
	    bool flag=0;
	    for(int j=1;j<=n;j++){
	        char s[maxn];
	        scanf("%s",s);
	        add(s);
	        if(find(s)){flag=1;break;}
	    }
	    flag?puts("NO"):puts("YES");
	}
	return 0;
 } 
2020/5/26 10:39
加载中...