前三题略
T4：
题目描述
小A有n个长度都是L的字符串。这些字符串只包含前8个小写字符，'a'~'h'。但这些字符串非常的混乱，它们几乎长得互不相同。小A想通过一些规则，让它们长得尽可能相同。小A现在有K次机会，他可以每次机会，可以选择一对字符x,y，让x,y变成等价的字符（注意这里x,y和字符'x', 'y'不是一样的，只是个代号）。注意，等价关系是有传递性的。比如小A让'a'和'b'等价， 'b'和'c'等价，那么'a'和'c'等价。
对于两个长度字符串P,Q是等价的，当且仅当对于每一位，P的字符和Q的字符都是等价的。
小A希望你告诉他，要怎么利用好这K次机会（当然可以不用完），使得尽可能多对字符串是等价的。注意每对字符串只能算一次。
数据包含10个数据点。每个数据点可能有不同的特性。
对于第1，2个数据点： 保证每个字符串只包含前4个小写字母
对于第3，4个数据点：每个字符串都只包含一种字母
对于第5，6个数据点：n<=10,L<=100
对于所有数据，满足：n <= 100, L <= 1000，K <= 28，每个字符串只包含前8个小写字母
对于第1，2个数据点： 保证每个字符串只包含前4个小写字母
对于第3，4个数据点：每个字符串都只包含一种字母
对于第5，6个数据点：n<=10,L<=100
对于所有数据，满足：n <= 100, L <= 1000，K <= 28，每个字符串只包含前8个小写字母
题解：
普及组字符串？？？
肯定枚举了。
关键点，只有8个字符！！
K=28 有什么用？最多只要7个，就可以把所有都等价，就是n*(n-1)/2了。
所以，相当于是把a~h放进8-k个箱子里，每个箱子中的字符都是等价的。
第二类斯特林数，最多1701种情况。
枚举即可。
判断？
同一个箱子里的字符，干脆就是箱子编号算了。
直接比较肯定爆炸。
hash了。
但是，每次hsh一遍 ，1701*n*L只有60分
关键点还是只有8个字符！！
哈希本质还是一个P进制数
所以，对于每一个字符串的哈希，其实是每个字符作为这一位的数拼成的。
不一定每次必须要顺序从左到右，只要char * base^i做对，就可以嘛。
所以，可以记录下来，对于每一个字符串s，每一个字符c，c在s中出现的所有位置的base^i的和，可以预处理。
然后，每次判断的时候，
每个字符hsh就不用O（L）扫了。直接通过枚举每个字符的现在值，乘上预处理的base们和，再做和即可！
就O(8）处理一个串的哈希值了。
然后就 轻轻松松AC
代码：
注意箱子枚举的方法。
可以严格O（1701）处理，节省时间。
判断往之前箱子放，和新开箱子是有条件的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=;
const int M=;
const int mod=1e9+;
const ll P=; int n,l,k;
char a[N][M];
map<ll,int>mp;
ll mi[M];
ll sum[N][];
ll be[];
int sz[];
int ans=;
void dfs(int x,int box){
if(x==){
mp.clear();
int alike=;
bool fl=false;
for(int i=;i<=n;i++){
ll hsh=;
for(int j=;j<=;j++){
(hsh+=sum[i][j]*be[j])%=mod;
}
alike+=mp[hsh];
mp[hsh]+=;
} ans=max(ans,alike);
return;
}
if(-x>=k-box){
for(int i=;i<=box;i++){
be[x]=i;
sz[i]++;
dfs(x+,box);
be[x]=;
sz[i]--;
}
}
if(box<k&&sz[box]){
be[x]=box+;
sz[box+]++;
dfs(x+,box+);
be[x]=;
sz[box+]--;
}
}
int main()
{
scanf("%d%d%d",&n,&l,&k);
k=max(-k,);
for(int i=;i<=n;i++){
scanf("%s",a[i]+);
}
mi[]=;
for(int i=;i<=l;i++){
mi[i]=(mi[i-]*P)%mod;
}
for(int i=;i<=n;i++){
for(int j=;j<=l;j++){
(sum[i][a[i][j]-'a']+=mi[j])%=mod;
}
}
dfs(,);
printf("%d",ans);
return ;
}
总结：
这个题非常好的抓住了哈希的本质！
哈希是一个映射，但是本质是一个P进制数。
再利用8个字符的条件，就可以通过预处理，分着把hsh快速算出来了！
（以后如果碰到什么26个字符，但是长度很长，而且要重复hsh多次的，也许可以用上
而且是所有的一类字符变成另一类的那种。
）