学步园

题目链接：点击打开链接

题目大意：一列 数串（likely more than 30 digits），分成几组，每组都是严格单减顺序。

题目分析：分析到最后，其实就是找重复最多的数就是组数，但是数的范围差别太大，一定对数进行处理。

                    接触到BKDR hash 先写借鉴大神的博客点击打开链接

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#define maxn  249997
int ans,hash[maxn];
unsigned int BKDRHash(char *str)
{
    unsigned int seed=131 ;// 31 131 1313 13131 131313 etc..
    unsigned int hash=0 ;

    while(*str)
    {
        hash=hash*seed+(*str++);
    }

    return hash%maxn;
}
void solve(char *str)
{
    int t;
    while(*str=='0') str++;
    t=BKDRHash(str);
    if(hash[t]==-1) hash[t]=1;
    else hash[t]++;
    if(ans<hash[t]) ans=hash[t];
}

int main()
{
    int n;
    char str[50];
    while(scanf("%d",&n)!=EOF)
    {
        memset(hash,-1,sizeof(hash));
        getchar();
        ans=1;
        while(n--)
        {
           gets(str);
           solve(str);
        }
        printf("%d\n",ans);
    }
    return 0;
}

题目总总结：

1.确定mod的数P，或者HASH 的数组范围P原则：P<=表长maxn（可事先进行，即hash后的范围），p为素数，或则至少不明显的合数，不含20以下的质因子

2.unsigned int 输出为%u = =

下面附上某牛的代码比我的代码的更加强，判错更严谨

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#define maxn 249997
using namespace std;
int hash[maxn],coun[maxn];
int ans;
unsigned int BKDRHash(char*str)
{
    unsigned int seed=131 ;// 31 131 1313 13131 131313 etc..
    unsigned int hash=0 ;

    while(*str)
    {
        hash=hash*seed+(*str++);
        //printf("*%u*\n",hash);
    }

    return(hash % maxn);
}
void hashit(char *str)
{
  int k,t;
  while(*str=='0') str++;
  k=BKDRHash(str);//返回一个整型的状态
  //printf("k=%d\n",k);观察maxn的范围
  t=k%maxn;
  while(hash[t]!=-1&&hash[t]!=k)
  t=(t+10)%maxn;
  if(hash[t]==-1)  hash[t]=k,coun[t]=1;
  else
  {
    //system("pause");
    coun[t]++;
    if(coun[t]>ans)  ans=coun[t];
  }
}
int main()
{
  int N;
  char str[50];
  while(scanf("%d",&N)!=EOF)
  {
    memset(hash,-1,sizeof(hash));
    ans=1;
    getchar();
    while(N--)
    {
      gets(str);
      hashit(str);
    }
    printf("%d\n",ans);
  }
}

其他相关资料借鉴：

真是非常好的学习资料

1.http://blog.csdn.net/v_JULY_v/article/details/6256463#comments

2.http://blog.csdn.net/v_july_v/article/details/7085669

3.http://blog.csdn.net/gdujian0119/article/details/6777239