HDU 1800 Flying to the Mars

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

原题目链接HDU1800


分类

HDU 字典树


题意

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

样例输入输出

Sample Input

  1. 4
  2. 10
  3. 20
  4. 30
  5. 04
  6. 5
  7. 2
  8. 3
  9. 4
  10. 3
  11. 4

Sample Output

  1. 1
  2. 2

想法

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


代码

280ms

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #define maxn 11111
  7. using namespace std;
  8. struct Trie{
  9. int ch[maxn][10];
  10. int val[maxn];
  11. int sz;//结点个数
  12. Trie(){
  13. sz = 1;
  14. memset(ch[0],0,sizeof(ch[0]));
  15. memset(val,0,sizeof(val));
  16. }
  17. int idx(char c){
  18. return c - '0';
  19. }
  20. int insert(char* s){
  21. int u=0 , n= strlen(s);
  22. int j=0;
  23. while(s[j]=='0')j++;
  24. for(int i=j;i<n;i++){
  25. int c = idx(s[i]);
  26. if(!ch[u][c])//结点不存在
  27. {
  28. memset(ch[sz],0,sizeof(ch[sz]));
  29. ch[u][c] = sz++;
  30. }
  31. u = ch[u][c];
  32. }
  33. val[u]++;
  34. return val[u];
  35. }
  36. };
  37. int main()
  38. {
  39. int n,mmax;
  40. char str[44];
  41. while(~scanf("%d",&n)){
  42. Trie T;
  43. mmax = 0;
  44. while(n--){
  45. scanf("%s",str);
  46. int t = T.insert(str);
  47. mmax= max(mmax,t);
  48. }
  49. if(mmax == 0)
  50. mmax = 1;
  51. printf("%d\n",mmax);
  52. }
  53. return 0;
  54. }

发表评论

表情:
评论列表 (有 0 条评论,196人围观)

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

相关阅读

    相关 Fly

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

    相关 HDU 5385 The path

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

    相关 HDU 5307 He is Flying【FFT】

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