HDU 1800 Flying to the Mars

末蓝、 2022-04-16 04:57 112阅读 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

发表评论取消回复

表情：

评论列表（有 0 条评论，112人围观）

还没有评论，来说两句吧...

相关阅读

相关 Flying to the Mars

[B - Flying to the Mars][] [HDU - 1800 ][HDU - 1800] /\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

分手后的思念是犯贱/ 2024年02月18日 22:08/ 0 赞/ 55 阅读

相关 Flying to the Mars HDU - 1800(字典树）

Flying to the Mars HDU - 1800 题目链接：[https://vjudge.net/problem/HDU-1800][https_vjudge

系统管理员/ 2023年08月17日 15:41/ 0 赞/ 117 阅读

相关 Fly

转载至 [这位大佬][Link 1] Fly.js 是一个基于 promise 的，轻量且强大的Javascript http 网络库，它有如下特点：提供统一的 Pr

冷不防/ 2022年11月07日 04:25/ 0 赞/ 136 阅读

相关 HDU 5385 The path

如果我们知道每个点的dis值和最短路径树的话，方案是很容易构造的我们可以采取贪心做法，一开始将1号点作为最短路径树的根，然后左边从2开始，右边从n开始，只要之前加入的点有边

待我称王封你为后i/ 2022年08月04日 00:47/ 0 赞/ 21 阅读

相关 HDU 5307 He is Flying【FFT】

题意：有n段路，每段路长度为si，你从节点i到节点j，可以获得一个开心值j−i\+1，然后问你，主人公走过了所有总长度为s的段，问你有多少开心值。思路：首先想

灰太狼/ 2022年08月02日 14:48/ 0 赞/ 8 阅读

相关 To The Max

To The Max Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Jav

秒速五厘米/ 2022年07月31日 20:27/ 0 赞/ 150 阅读

相关 To The Max

Given a two-dimensional array of positive and negative integers, a sub-rectangle is any

迷南。/ 2022年06月12日 02:47/ 0 赞/ 120 阅读

相关 HDU 1800 Flying to the Mars

原题目链接[HDU1800][] -------------------- 分类 HDU 字典树 -------------------- 题意求出数

末蓝、/ 2022年04月16日 04:57/ 0 赞/ 113 阅读

相关学习flying logic

之前在知乎上结识的朋友吴笛，他的qq空间里分享了 flying logic的一些用途，我想到可以规划和团队的目标，这点让我感到很兴奋，分享学习这个软件。学习之前，我应当把软

偏执的太偏执、/ 2022年02月05日 00:39/ 0 赞/ 219 阅读

相关 To The Oak

To The Oak Shu ting If I love you I won't wind upon you like a trumpet creeper

た入场券/ 2021年12月16日 09:59/ 0 赞/ 182 阅读