Flying to the Mars_牛客博客

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

C++版本一

贪心

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int main()
{
    int n,i,max,t;
    int a[3005];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;++i)
            scanf("%d",&a[i]);
        sort(a,a+n);
        max=1;
        t=1;
        for(i=1;i<n;++i)
        {
            if(a[i]!=a[i-1])
                t=1;
            else 
                ++t;
            if(t>max)
                max=t;
        }
        printf("%d\n",max);
    }
    return 0;
}

C++代码二

字典树

#include<cstdio>
#include<cstring>
#include<stdlib.h>

struct node
{
    int sum;
    node *next[26];    
};
node memory[1000000];
int k;
int max;

void insert(char *t,node *T)
{
    int i,id,j;
    node *p,*q;
    p=T;
    i=0;
    while(t[i])
    {
        id=t[i]-'0';
        if(p->next[id]==NULL)
        {
        //    q=(node *)malloc(sizeof(node));
            q=&memory[k++];
            q->sum=0;
            for(j=0;j<26;++j)
                q->next[j]=NULL;
            p->next[id]=q;
        }
        p=p->next[id];
        ++i;
    }
    p->sum++;
    if(max<p->sum)
        max=p->sum;
}

int main()
{
    int n,i;
    char s[35];
    node *T;
//    T=(node *)malloc(sizeof(node));
    T=&memory[0];
    while(scanf("%d",&n)!=EOF)
    {
        max=0;
        k=1;
        T->sum=0;
        for(i=0;i<26;++i)
            T->next[i]=NULL;
        while(n--)
        {
            scanf("%s",s);
            i=0;
            while(s[i++]=='0');
            insert(&s[i-1],T);
        }
        printf("%d\n",max);
    }
    return 0;
}

C++版本三

字典树

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
struct Tree
{
    int num;
    Tree *next[10];
    Tree()
    {
        num=0;
        for(int i=0;i<10;i++)
        {
            next[i]=NULL;
        }
    }
}*root;
int insert(Tree *p,char *s)
{
    int i=0;
    while(s[i])
    {
        int x=s[i]-'0';
        if(p->next[x]==NULL)
        {
            p->next[x]=new Tree();
        }
        p=p->next[x];
        i++;
    }
    p->num++;
   // cout<<"数为:"<<p->num<<endl;
    return (p->num);
}
int main()
{
    char s[30],s1[30];
    int n,maxs,stl,i,len;
    while(cin>>n)
    {
        root=new Tree();
        maxs=-5;
        while(n--)
        {
            cin>>s;
            stl=strlen(s);
            i=len=0;
            for(i=0;i<stl;i++)
            {
                if(s[i]!='0')
                {
                    break;
                }
            }
            for(i;i<stl;i++)
            {
                s1[len++]=s[i];
            }
            s1[len]='\0';
          //  cout<<s1<<endl;
            maxs=max(maxs,insert(root,s1));
        }
        cout<<maxs<<endl;
    }
}

C++版本四

二分查找树/二叉排序树


#include <stdio.h>
#include <malloc.h>
struct node 
{
    int num;
    node *lc;
    node *rc;
    int time;
};
int max;
struct node *BST(struct node *root,int num)
{
    if (root==NULL)       //根节点为空 建立根节点
    {
        root=(struct node *)malloc(sizeof(struct node));
        root->lc=NULL;
        root->rc=NULL;
        root->num=num;
        root->time=1;
    }
    else 
    {
        if (root->num==num)        // 根的name 和 s相同，次数+1
        {
             root->time++;
             if (root->time>max) 
                 max=root->time;
        }
        else if (root->num>num)    // 根比s大，找左子树
            root->lc=BST(root->lc,num);
        else                      // 根比s小，找右子树
            root->rc=BST(root->rc,num);
    }
    return root;
} 
int main()
{
    int n,i,num;
    while (scanf("%d",&n)!=EOF)
    {
         struct node *root=NULL;
         max=1;
         for (i=0;i<n;i++)
         {
            scanf("%d",&num);
            root=BST(root,num);
         }
         printf ("%d\n",max);
    }
    return 0;
}

C++版本五

题解：map

每个串去掉一串最长的再去掉一串次长的。。。。。

到最后肯定剩下某个出现次数最多的数字所以本题就是找那个数字出现的最多最多的次数是多少

#include<stdio.h>
#include<map>
using namespace std;
int main()
{
	__int64 i,n,max;
	map<__int64,__int64>mp;
	while(scanf("%I64d",&n)!=EOF)
	{
		mp.clear();
		while(n--)
		{
			scanf("%I64d",&i);
			mp[i]++;
		}
		map<__int64,__int64>::iterator it;
		max=0;
		for(it=mp.begin();it!=mp.end();it++)
			if(max<it->second) max=it->second;
		printf("%I64d\n",max);
	}
	return 0;
}

C++版本六

字典树

TLEing

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=700000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp;
int a[N][10];
char str[50];
int sum[N];
void init(){
    memset(a,0,sizeof(a));
    memset(sum,0,sizeof(sum));
    cnt=0;
    ans=0;
}
int insert(char *num){
    int len=strlen(num),p=0;
    for(int i=0;i<len;i++){
        int tmp=num[i]-'0';
        if(a[p][tmp]==0)a[p][tmp]=++cnt;
        p=a[p][tmp];
    }
    sum[p]++;
    return sum[p];
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //scanf("%d",&n);
    //scanf("%d",&t);
    ios::sync_with_stdio(0);
    while(~scanf("%d",&n)){
        init();
        for(int i=1;i<=n;i++){
            scanf("%s",str);
            int pos=0;
            while(str[pos++]=='0');
            ans=max(ans,insert(&str[pos-1]));
        }
        cout<<ans<<endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}