HDU 1800 Flying to the Mars

末蓝、 2022-04-16 04:57 200阅读 0赞

## 原题目链接[HDU1800][] ##

--------------------

## 分类 ##

HDU 字典树

--------------------

## 题意 ##

求出数字出现最多的次数。当n=0时，输出1.

## 样例输入输出 ##

Sample Input

4
    10
    20
    30
    04
    5
    2
    3
    4
    3
    4

Sample Output

1
    2

--------------------

## 想法 ##

（字典树，涉及到高级数据结构）  
每一个数字最长30位，用longlong也没用，所以要用字符串存储，自然想到了字典树，当然还有其他解法，map（时间勉强过），哈希（不会）  
注意：题目中说000123和123是一个数字，即要除去前导的0，稍作处理即可

--------------------

## 代码 ##

280ms

#include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #define maxn 11111
    using namespace std;
    struct Trie{ 
    	int ch[maxn][10];
    	int val[maxn];
    	int sz;//结点个数
    	Trie(){ 
    		sz = 1;
    		memset(ch[0],0,sizeof(ch[0]));
    		memset(val,0,sizeof(val));
    	} 
    	int idx(char c){ 
    		return c - '0';
    	}
    	
    	int insert(char* s){ 
    		int u=0 ,  n= strlen(s);
    		int j=0;
    		while(s[j]=='0')j++;
    		for(int i=j;i<n;i++){ 
    			int c = idx(s[i]);
    			if(!ch[u][c])//结点不存在
    			{ 
    				memset(ch[sz],0,sizeof(ch[sz]));
    				ch[u][c] = sz++;
    			}
    			u = ch[u][c];
    		}
    		val[u]++;
    		return val[u];
    	}
    };
    
    int main()
    { 
    	int n,mmax;
    	char str[44];
    	while(~scanf("%d",&n)){ 
    		Trie T;
    		mmax = 0;
    		while(n--){ 
    			scanf("%s",str);
    			int t = T.insert(str);
    			mmax= max(mmax,t);
    		}
    		if(mmax == 0) 
    			mmax = 1;
    		printf("%d\n",mmax);
    	}
    	return 0;
    }

[HDU1800]: http://acm.hdu.edu.cn/showproblem.php?pid=1800