hdu——1671 phone list

短命女 2022-08-10 16:38 19阅读 0赞

首先想到的是用字典树存储号码，然后去查找每个输入的号码，判断是否存在一个单词词尾的节点值大于1；这就意味着他是某个单词的前缀，不过很不辛TLE......

#include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    using namespace std;
    struct Trie
    {
    	int v;
    	Trie *next[10];
    };
    Trie root;
    void creatTrie(char *str)
    {
    	Trie *p=&root,*q;
    	int len=strlen(str),i;
    	for(i=0;i<len;i++)
    	{
    		int id=str[i]-'0';
    		if(p->next[id]==NULL)
    		{
    			q=(Trie *)malloc(sizeof(root));
    			for(int j=0;j<10;j++)
    			q->next[j]=NULL;
    			q->v=1;
    			p->next[id]=q;
    			p=q;
    		}
    		else
    		{
    			p->next[id]->v++;
    			p=p->next[id];
    		}
    	}
    }
    int find(char *s)
    {
    	Trie *p=&root;
    	int len=strlen(s);
    	for(int i=0;i<len;i++)
    	{
    		int id=s[i]-'0';
    		p=p->next[id];
    	}
    	return p->v;
    }
    char p_num[10001][12];
    int main()
    {
    	int t,n;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d",&n);
    		for(int i=0;i<10;i++)
    		root.next[i]=NULL;
    		for(int i=0;i<n;i++)
    		{
    			scanf("%s",p_num[i]);
    			creatTrie(p_num[i]);
    		}
    		int sign=1;
    		for(int i=0;i<n;i++)
    		if(find(p_num[i])>1)
    		{
    			printf("NO\n");
    			sign=0;
    			break;
    		}
    		if(sign)printf("YES\n");
    	}
    	return 0;
    }

然后，又查了查字典树原来字典树还可以用来判断是否树中有当前单词的前缀，就改了上面的代码，结果还是TLE......（别人都过了的......)

#include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    using namespace std;
    struct Trie
    {
    	int v;
    	Trie *next[10];
    };
    
    Trie root;	int sign;
    
    void creatTrie(char *str)
    {
    	Trie *p=&root,*q;
    	int len=strlen(str),i;
    	for(i=0;i<len;i++)
    	{
    		int id=str[i]-'0';
    		if(p->next[id]==NULL)
    		{
    			q=new Trie;
    			for(int j=0;j<10;j++)
    			q->next[j]=NULL;
    			q->v=0;
    			p->next[id]=q;
    			p=q;
    		}
    		else
    		{
    			p=p->next[id];
    			if(p->v==1||str[i]=='\0')
    			sign=0;
    		}
    	}
    	p->v=1;
    }
    
    int main()
    {
    	int t,n;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d",&n);
    		for(int i=0;i<10;i++)
    		root.next[i]=NULL;
    		sign=1;char num[12];
    		for(int i=0;i<n;i++)
    		{
    			scanf("%s",num);
    			if(sign)creatTrie(num);
    		}
    		if(sign)printf("YES\n");
    		else 	printf("NO\n");
    	}
    	return 0;
    }

最后没办法了，先把号码按字典序排序，查找相邻项判断是否有前缀关系，有则输出否，判断全部后无则输出是；也怕超时，可是他却过了.........

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    
    char phone[10000][12];
    int cmp(const void* s1,const void* s2)
    {
        return strcmp((char*)s1,(char*)s2);
    }
    
    int main(void)
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            int i,n;
            bool flag=false;
            scanf("%d",&n);
            for(i=0;i<n;i++)
            {
                scanf("%s",phone[i]);
            }
            qsort(phone,n,sizeof(phone[0]),cmp);
            for(i=0;i<n-1;i++)
            {
                if(strncmp(phone[i],phone[i+1],strlen(phone[i]))==0)
                {
                    flag=true;
                    break;
                }
            }
            if(flag==false)
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }