题意:看LCY的课件,脱去题的马甲,意思就是求最有多少个重复的数字,数字要去掉前导零。
思路:hash
#include<iostream> #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++); } return(hash % maxn); } void hashit(char *str) { int k,t; while(*str=='0') str++; k=BKDRHash(str);//返回一个整型的状态 //printf("k=%d\n",k); 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); } }