Let the Balloon Rise

5
green
red
blue
red
red
3
pink
orange
pink
0

red
pink

AC1字典树：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define INF 0x7fffffff;
struct node
{
    int x;
    node *next[26];
    node()
    {
        x=0;
        memset(next,0,sizeof(next));
    }
};
node *root=NULL;

void insert(char *s)
{
    node *p=root;
    int i,k;
    for(i=0;i<strlen(s);i++)
    {
      k=s[i]-'a';
      if(p->next[k]==NULL)
          p->next[k]=new node;
      else
          p->next[k]->x++;
      p=p->next[k];
    }
}

int search(char *s)
{
    node *p=root;
    int i,k;
    for(i=0;i<strlen(s);i++)
    {
        k=s[i]-'a';
        if(p->next[k]==NULL)
         return 0;
          p=p->next[k];
    }
  return p->x;
}

char str[1010][30];
int main()
{
    
    int n;
    root=new node;
    while(scanf("%d",&n),n)
    {
        int i=0;
        memset(str,0,sizeof(str));
        for(i=0;i<n;i++)
        {
          scanf("%s",str[i]);
          insert(str[i]);
        }
        
       int ma=-INF;
       int j=0;
       for(i=0;i<n;i++)
       {
        int k=search(str[i]);
           if(k>ma)
           {
            ma=k;
         j=i;    
        }
            
       }
       printf("%s\n",str[j]); 
    }
    return 0;
}

AC2 模拟：

#include<cstdio>
#include<string.h>
#include<stdlib.h>
const int max= 1000+10;
char ba[max][20];
int b[max];

int main()
{
    int N;
    while(scanf("%d",&N),N)
    {
        int i,j;
        
        memset(ba,0,sizeof(ba));
        getchar();
        for(i=0;i<N;i++)
          scanf("%s",ba[i]);
         
         memset(b,0,sizeof(b)); 
          for(i=0;i<N;i++)
              for(j=i+1;j<N;j++)
                 if(strcmp(ba[i],ba[j])==0)
                   b[i]++;
                   
            int m=0,t;
            for(j=0;j<N;j++)
                if(m<=b[j])
                  m=b[j];
        
            for(i=0;i<N;i++)
                  if(b[i]==m)
                        {
                      printf("%s\n",ba[i]);
                        break;
                    }
                 
    }
    system("pause");
    return 0;
}

hdoj 1004 Let the Balloon Rise(模拟 || 字典树)

原文：http://blog.csdn.net/lh__huahuan/article/details/45111125