Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

字典树,1A

Posted by husanfeng at 2013-01-24 16:20:27 on Problem 3630 and last updated at 2013-01-24 16:24:36
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>

using namespace std;

struct node
{
    bool end;   
    int a[10];
};

bool x;
int ptr;
node list[100000];

void Init()
{
    x=true;
    ptr=0; 
    for(int i=0;i<100000;i++)
    {
        list[i].end=false;   
        for(int j=0;j<10;j++)
            list[i].a[j]=-1;
    }
}

void Insert(char*s)
{
    bool z=false; 
    bool y=false;
    int now=0;
    int len=strlen(s);
    for(int i=0;i<len;i++)
    {
        if(list[now].a[s[i]-'0']==-1)
        {   
            z=true;                      
            list[now].a[s[i]-'0']=++ptr;
            now=ptr;
        }           
        else
        {
            now=list[now].a[s[i]-'0'];
            if(list[now].end) y=true;
        }
    }
    list[now].end=true;
    x=(!y)&&z;                                       
}
               
int main()
{
    int t,n;
    char s[11];
    scanf("%d",&t);
    while(t--)
    {
        Init();
        scanf("%d",&n);
        while(n--)
        {
            scanf("%s",&s);
            if(x) Insert(s);
        }
        if(x) printf("YES\n");
        else printf("NO\n");
    }                        
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator