【傳送門：BZOJ3555】

---

簡要題意：

　　給出n個(gè)字符串長度為m，給出字符串的字符種數(shù)，求出相似的字符串個(gè)數(shù)

　　相似字符串的定義為：相同位置上兩個(gè)字符串有且只有一個(gè)字符不相同時(shí)，兩個(gè)字符串相似

---

題解：

　　亂搞搞，因?yàn)轭}目描述中說明會(huì)給出字符種數(shù)，就把各種字符按照出現(xiàn)的順序編一下號(hào)，然后我就想成是（字符種數(shù)+1）進(jìn)制來做，先處理一下前綴和，后綴和，然后枚舉i，表示第i位不同，那么我們就先忽略第i位的字符，然后保存左邊的字符串和右邊的字符串（用（字符種數(shù)+1）進(jìn)制來表示），然后按照左邊的大小排序，左邊相同時(shí)，按照右邊的大小排序，然后就判斷左右都相等的字符串的個(gè)數(shù)

　　注意假設(shè)當(dāng)前我們得到了有x個(gè)字符串是相等的時(shí)候，那么相似的個(gè)數(shù)為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; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/Never-mind/p/7878869.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ3555: [Ctsc2014]企鹅QQ的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。