题意:找出题给的最少的递增序列(严格递增)的个数，其中序列中每个数字不多于30位；序列长度不长于3000；
input:
4 (n)
10
20
30
04
output
1
思路:将节目转化为相同数的最多个数即可~~
这时就随便怎么搞了。我是直接用了map(开始不会hash啊…)来找mx;
但是和字符串hash相比，时间性能不好。
之后看了ACdreamers，学习了ELFhash之后发现挺好用的~~下面将讲解一下我对ELFhash的理解。
// 702ms 1808k
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i < (n);i++)
map<string,int> mp;
int main()
{
ios_base::sync_with_stdio(false);cin.tie();cout.tie();cerr<<"";
int n,i;
while(cin>>n){
mp.clear();
string str;
rep(i,n){
cin>>str;
int j = ;
for(;j < str.size();j++)if(str[j] != '') break;
mp[str.substr(j)]++;
}
int ans = ;
for(auto m : mp){
ans = max(ans , m.second);
}
cout<<ans<<endl;
}
}
ELFhash:
hash要对字符串里面的每一个字符进行运算，之后得到一个”相对”不同的值(因为有冲突)；字符有八个字节的，但是里面对高位的四个字节与前一个字符的低的四个字节相加了，低的四个字节填补了h左移空出来的四个字节(不知理解得是否有误，若有误，请指正~)并且里面的位是从0开始的，即当h<<4时开始的0位，现在就是第4位了。里面的hash运算还有就是在h要满的时候(即h的高四位28~31不为0时)，下一次再加进字符时，就会直接移走了，但是算法要将这高四位和4~8位的数再做一次XOR运算，应该是使得得到的hash更随机~~(里面0xF0000000L就表示28~31位全是1，其余位为0)
hash::code @ACdreamers
499ms
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i < (n);i++)
#define MS0(a) memset(a,0,sizeof(a))
const int MOD = ;
int Hash[MOD],cnt[MOD];
unsigned int ELFhash(char *str)//unsigned
{
unsigned int h = ;
unsigned int x;
while(*str){
h = (h << ) + *str++;//与前一个字符的第四位字节相加；
x = h & 0xF0000000L;//x为h的28~31位
if(x){
h ^= x>>; //高四位和4~8位的数再做一次XOR运算，不然没运算就移走了，可惜~
h &= ~x;// h清空28~31位(运算完了)
}
}
return h & 0x7FFFFFFF;//返回unsigned，即0x7FFFFFFF为unsigned的二进制全为1
}
int Hashhit(char *str)
{
while(*str == '') str++;
int k = ELFhash(str);
int t = k % MOD;
while(Hash[t] && Hash[t] != k) //解决冲突；
t = (t + )%MOD;
if(Hash[t] == )
Hash[t] = k;
return ++cnt[t];
}
int main()
{
int n;char str[];
while(scanf("%d",&n) == ){
MS0(Hash);MS0(cnt);
int ans = ;
rep(i,n){
scanf("%s",str);
ans = max(ans,Hashhit(str));
}
printf("%d\n",ans);
}
}