BZOJ3555: [Ctsc2014]企鵝QQ

【傳送門：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\n",ans);return 0;
}

?

?