poj2418map或者字典树

题意：

给你一些串，然后求出每个串出现的概率。

思路：

简单题目，做法也很多，我用字典树做了下，然后又用map做了下，其实这个题目我感觉直接排序一遍之后线性输出应该是最简单最快的（这个没敲），就是只是排序的时间复杂度而已O(n*log(n)*len)字典序的排序时间复杂度记得*len.

字典树829MS

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<algorithm>

using namespace std;

typedef struct Tree

{

    Tree *next[129];

    int v;

}Tree;

typedef struct

{

    char s[32];

}SS;

Tree root;

SS S[10005];

bool camp(SS a ,SS b)

{

    return strcmp(a.s ,b.s) < 0;

}

void BuidTree(char *str)

{

    int len = strlen(str);

    Tree *p = &root ,*q;

    for(int i = 0 ;i < len ;i ++)

    {

        int id = str[i];

        if(p -> next[id] == NULL)

        {

            q = (Tree *)malloc(sizeof(root));

            q -> v = 0;

            for(int j = 0 ;j <= 128 ;j ++)

            q -> next[j] = NULL;

            p -> next[id] = q;

            p = p -> next[id];

        }

        else p = p -> next[id];

    }

    p -> v ++;

}

int Query(char *str)

{

    int len = strlen(str);

    Tree * q = &root;

    for(int i = 0 ;i < len ;i ++)

    {

        int id = str[i];

        q = q -> next[id];

        if(q == NULL) return 0;

    }

    return q -> v;

}

int main ()

{

    int i ,n ,id;

    char str[35];

    n = id = 0;

    for(i = 0 ;i <= 128 ;i ++)

    root.next[i] = NULL;

    while(gets(str))

    {

        if(!Query(str))

        {

            id ++;

            int len = strlen(str);

            for(int j = 0 ;j <= len ;j ++)

            S[id].s[j] = str[j];

        }

        BuidTree(str);

        n ++;

    }

    sort(S + 1 ,S + id + 1 ,camp);

    for(i = 1 ;i <= id ;i ++)

    printf("%s %.4lf\n" ,S[i].s ,Query(S[i].s) * 100.0 / n);

    return 0;

}

map 1500ms

#include<map>

#include<string>

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

typedef struct

{

    char s[35];

}SS;

SS S[10005];

map<string ,int>mark;

bool camp(SS a ,SS b)

{

    return strcmp(a.s ,b.s) < 0;

}

int main ()

{

    mark.clear();

    char str[35];

    int id = 0 ,n = 0;

    while(gets(str))

    {

        if(mark[str] ++ == 0)

        {

            int len = strlen(str);

            id ++;

            for(int i = 0 ;i <= len ;i ++)

            S[id].s[i] = str[i];

        }

        n ++;

    }

    sort(S + 1 ,S + id + 1 ,camp);

    for(int i = 1 ;i <= id ;i ++)

    {

        printf("%s %.4lf\n" ,S[i].s ,mark[S[i].s] * 100.0 / n);

    }

    return 0;

}

巴特西

poj2418map或者字典树

最新文章

热门文章