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

C++静态建树!!

Posted by 1214011013 at 2014-09-29 21:07:47 on Problem 3630
/*
考察了字典树的操作,刚开始我是动态建树的,好遗憾
竟然超时了,所以采取了静态建树的方式
注意输入顺序 假如有 110002 和 110
要考虑两种情况
110002
110
与
110
110002;
这两种情况 其他的就没傻了
*/
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <algorithm>
using namespace std;
int Count;
struct Trie
{
    Trie * next[10];
    bool flag;//标记是否是结尾
    int cnt;
    Trie()
    {
        for(int i = 0; i < 10; i++)
            next[i] = NULL;
        flag = false;
        cnt = 0;
    }
};
Trie memory[600050];

Trie * root = NULL;//根节点
bool Insert(char msg[])
{
    int i = 0;
    Trie * cur = root;
    int k;
    while(msg[i])
    {
        int k = msg[i] - '0';
        if(cur->next[k] == NULL)
            cur->next[k] =  &memory[Count++];//new Trie();//创建新结点
        else
        {
            cur->next[k]->cnt++;
            if(cur->next[k]->flag)
                return false;
        }
        cur = cur->next[k];
        i++;
    }
    cur->flag = true;
    if(cur->cnt>=1)
        return false;
    return true;
}
/*
void Delete(Trie * root)
{
    for(int i = 0; i < 10; i ++ )
    {
        if(root->next[i] != NULL)
            Delete(root->next[i]);
    }
    delete root;
}
*/
int  t;
int n;
int main()
{
    scanf("%d",&t);
    char msg[12];

    while(t--)
    {
        Count = 0;
        scanf("%d",&n);
        memset(memory,0,sizeof(memory));
        root =&memory[Count++];// new Trie();
        bool flag = true;
        for(int i = 0; i < n; i++)
        {
            scanf("%s",msg);
            if(flag)
               flag =  Insert(msg);
        }
        if(!flag)
            printf("NO\n");
        else
            printf("YES\n");
          //  Delete(root);
    }
    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