【传送门：BZOJ3555】
简要题意：
给出n个字符串长度为m，给出字符串的字符种数，求出相似的字符串个数
相似字符串的定义为：相同位置上两个字符串有且只有一个字符不相同时，两个字符串相似
题解：
乱搞搞，因为题目描述中说明会给出字符种数，就把各种字符按照出现的顺序编一下号，然后我就想成是（字符种数+1）进制来做，先处理一下前缀和，后缀和，然后枚举i，表示第i位不同，那么我们就先忽略第i位的字符，然后保存左边的字符串和右边的字符串（用（字符种数+1）进制来表示），然后按照左边的大小排序，左边相同时，按照右边的大小排序，然后就判断左右都相等的字符串的个数
注意假设当前我们得到了有x个字符串是相等的时候，那么相似的个数为x*(x-1)/2
题目20s，19s跑过去，RP++
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; char st[210]; LL l[31000][210]; LL r[31000][210]; struct node { LL l,r; }cnt[31000]; LL cc[210]; int cmp(const void *xx,const void *yy) { node n1=*(node *)xx; node n2=*(node *)yy; if(n1.l<n2.l) return -1; if(n1.l>n2.l) return 1; if(n1.r<n2.r) return -1; if(n1.r>n2.r) return 1; return 0; } int main() { int n,m,d; scanf("%d%d%d",&n,&m,&d); memset(cc,0,sizeof(cc)); int len=0; for(int i=1;i<=n;i++) { scanf("%s",st+1); for(int j=1;j<=m;j++) if(cc[st[j]]==0) cc[st[j]]=++len; l[i][0]=0;r[i][m+1]=0; for(int j=1;j<=m;j++) l[i][j]=l[i][j-1]*(d+1)+cc[st[j]]; for(int j=m;j>=1;j--) r[i][j]=r[i][j+1]*(d+1)+cc[st[j]]; } int ans=0; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) cnt[j].l=l[j][i-1],cnt[j].r=r[j][i+1]; qsort(cnt+1,n,sizeof(node),cmp); int dd=1; for(int j=2;j<=n;j++) { if(cnt[j].l==cnt[j-1].l&&cnt[j].r==cnt[j-1].r) dd++; else { ans+=dd*(dd-1)/2; dd=1; } } ans+=dd*(dd-1)/2; } printf("%d ",ans); return 0; }