论一类脑筋急转弯题和奇技淫巧题的解题技巧
【题意】
给定n个长为m且只包含xyz的字符串，定义两个字符串的相似程度为它们对应位置相同字符个数(比如xyz和yyz的相似程度为2，后两位相同)，分别求出相似度为0~m的无序字符串对数。
【样例】
输入：
4 3
xyz
xyz
zzx
xzz
输出：
2
1
2
1
解释：
(xyz,zzx)(xyz,zzx)相似度为0，(zzx,xzz)相似度为1，(xyz,xzz) (xyz,xzz)相似度为2，(xyz,xyz)相似度为3。
【数据范围与约定】
共20个测试点。
对于测试点1，n<=10。
对于测试点2,3，n*m≤1000。
对于测试点4，所有单词都相同。
对于测试点5，m＝1。
对于测试点6~10，所有单词只包含x和y这两个字符。
对于全部测试点，n*m<=100000。
注意时间限制是3s。
【解法】
不得不说这个题的解法真特么机智……脑筋急转弯……
先想暴力，暴力枚举C(n,2)个字符串对，每个对都用O(m)的时间暴力比较，复杂度O(nm)。
观察一下数据范围，n*m<=100000。换句话说，m>30的时候直接暴力即可(经计算m=31时nm=322419375，况且还有0.5的常数，实测无压力)。剩下的就只有m<=30的情况了。
如果换个方向考虑，可以发现字符串的种类是有限的(最多3种)。所以，可以尝试对字符串三进制状压，然后只需枚举一遍字符串并从之前的所有3种字符串中枚举获得答案即可。这样的复杂度是O(n3)，对于m=30的情况来说实在是太大了，经计算大概只能到m=7~8的级别(m=8时n3=82012500，m=9时n3=328036878，由于三进制常数比较大，实际上m=7的时候就已经T了，当然你也可以用四进制减小常数)。
这样就麻烦了，m<7的时候可以三进制暴力，m>30的时候可以直接暴力，中间那些7<=m<=30的情况怎么搞？
回过头来看暴力，对于每个字符串对我们是用暴力比较的方式得出相似度的。但其实没这个必要，m<=30的时候完全可以把它压成三个二进制数x,y,z，分别表示对应位为x,y,z的下标集合。这样比较的时候就可以用二进制位运算O(1)得出两串的相同部分的集合(也是二进制数)，再O(1)数出里面的1的个数，比较就压到O(1)了。至于统计1个数，我用的是14年沈洋论文里的递推法，具体可以看沈洋的论文。
最后总结解法：
对于不同的m分类讨论。
m<7时，三进制状压暴力。
7<=m<=30时，压位后暴力。
m>30时，直接暴力。
贴个代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#define cntone(x) ((one[((x)&(65535))])+(one[((x)>>(16))]))
using namespace std;
const int maxn=;
int n,m,one[maxn]={},cnt[maxn]={},x[maxn],y[maxn],z[maxn],pw[maxn];
long long ans[maxn]={};
char c[maxn];
string s[maxn];
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%s",c);
s[i]=c;
}
if(m<){
pw[]=;
for(int i=;i<=m;i++)pw[i]=pw[i-]*;
for(int i=;i<=n;i++){
int val=;
for(int j=;j<m;j++)val=val*+s[i][j]-'x';
for(int k=;k<pw[m];k++){
int tmp=;
for(int j=;j<m;j++)if((k/pw[j])%==(val/pw[j])%)tmp++;
ans[tmp]+=cnt[k];
}
cnt[val]++;
}
}
else if(m<){
for(int i=;i<;i++)one[i]=one[i>>]+(i&);
for(int i=;i<=n;i++){
for(int j=;j<m;j++){
if(s[i][j]=='x')x[i]|=<<j;
else if(s[i][j]=='y')y[i]|=<<j;
else z[i]|=<<j;
}
for(int j=;j<i;j++)ans[cntone((x[i]&x[j])|(y[i]&y[j])|(z[i]&z[j]))]++;
}
}
else{
for(int i=;i<=n;i++)for(int j=;j<i;j++){
int tmp=;
for(int k=;k<m;k++)if(s[i][k]==s[j][k])tmp++;
ans[tmp]++;
}
}
for(int i=;i<=m;i++)printf("%lld\n",ans[i]);
return ;
}
【后记】
好像m>30的时候也可以压位优化(多压几个int)，不过懒得写了。
这题真特么脑筋急转弯……被今天的三道脑筋急转弯题坑惨了……