前三题略

 

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个小写字母

 

题解：

普及组字符串？？？

肯定枚举了。

 

关键点，只有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
       
        using namespace std;typedef long long ll;const int N=105;const int M=1005;const int mod=1e9+7;const ll P=13331; int n,l,k;char a[N][M];map
        
         mp;ll mi[M];ll sum[N][8];ll be[8];int sz[8];int ans=0;void dfs(int x,int box){    if(x==8){        mp.clear();        int alike=0;        bool fl=false;        for(int i=1;i<=n;i++){            ll hsh=0;            for(int j=0;j<=7;j++){                (hsh+=sum[i][j]*be[j])%=mod;               }            alike+=mp[hsh];            mp[hsh]+=1;        }        ans=max(ans,alike);        return;    }    if(7-x>=k-box){        for(int i=1;i<=box;i++){            be[x]=i;            sz[i]++;            dfs(x+1,box);            be[x]=0;            sz[i]--;        }    }    if(box
        
       

 

总结：

这个题非常好的抓住了哈希的本质！

哈希是一个映射，但是本质是一个P进制数。

再利用8个字符的条件，就可以通过预处理，分着把hsh快速算出来了！

（以后如果碰到什么26个字符，但是长度很长，而且要重复hsh多次的，也许可以用上

而且是所有的一类字符变成另一类的那种。

）