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

献上数组写法 141MS

Posted by 1007783493 at 2016-08-23 23:40:58 on Problem 3630
//3208K 141MS
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define clr( a , x ) memset ( a , x , sizeof (a) );
#define RE freopen("in.txt","r",stdin);
#define WE freopen("out.txt","w",stdout);

const int maxn = 10000 * 13 + 5;
const int maxch = 11;
struct tree
{
    int next[maxn][maxch];
    bool leaf[maxn];
    int cnt, root;

    int newNode() {
        memset(next[cnt], -1, sizeof(next[cnt]));
        return cnt++;
    }
    void init() {
        cnt = 0;
        root = newNode();
        memset(leaf, false, sizeof(leaf));
    }
    bool insert(char *s1) {
        int len = strlen(s1);
        int cur = root;
        for (int i = 0; i < len; ++i) {
            int id = s1[i] - '0';
            if (next[cur][id] == -1) {
                next[cur][id] = newNode();
            }
            if (leaf[cur]) return true;
            cur = next[cur][id];
        }
        leaf[cur] = true;

        //如果当前串后面还有则说明该串是某串的前缀
        for (int i = 0; i < maxch; ++i){
            if(next[cur][i] != -1) return true;
        }
        return false;
    }
} trie;
int main() {
    // RE
    int t, n;
    char s1[12];
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        bool done = false;
        trie.init();
        for (int i = 0; i < n; ++i) {
            scanf("%s", s1);
            if (trie.insert(s1)) { done = true;}
        }
        if (done) printf("NO\n");
        else printf("YES\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