本文主要是介绍【BZOJ3555】【Ctsc2014】企鹅QQ,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3555
题解:
先将所有字符串哈希
枚举删去哪一位上的字母,用哈希判重
删去第i为的字母对应的哈希值Hash=Hash-s[i]*base^(len-i)
注意不能把所有的放到一起做,否则“Penguin1”和“2Penguin”不能判断
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ULL unsigned long long
using namespace std;const int base=13331;
ULL p[205],a[30010],H[30010];
char s[30010][205];
int len,n,ans;int main()
{scanf("%d%d%*d",&n,&len);p[0]=1; for(int i=1;i<=len;i++) p[i]=p[i-1]*base;for(int i=1;i<=n;i++){scanf("%s",s[i]+1);for(int j=1;j<=len;j++) H[i]=H[i]*base+s[i][j]; }ans=0;for(int i=1;i<=len;i++){for(int j=1;j<=n;j++) a[j]=H[j]-s[j][i]*p[len-i];sort(a+1,a+n+1);int tmp=1;for(int i=2;i<=n;i++)if(a[i]==a[i-1]) ans+=tmp++;else tmp=1;}printf("%d\n",ans);return 0;
}
这篇关于【BZOJ3555】【Ctsc2014】企鹅QQ的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!