[BZOJ3555][Ctsc2014]企鹅QQ（hash）

2019-11-06 07:32:05

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

枚举每一位，把这一位去掉，hash统计有多少个一样的因为不存在两个串相同，所以不用管其它的直接搞就行 sort要快很多，map跑好慢…

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<map>using namespace std;#define UL unsigned long longconst UL p=2000001001LL;int n,l,ans;char s[30005][205];UL hash[30005],mi[205];map <UL,int> Cnt;int main(){ int lalala; scanf("%d%d%d",&n,&l,&lalala); for (int i=1;i<=n;++i) scanf("%s",s[i]); mi[0]=1LL;for (int i=1;i<=l;++i) mi[i]=mi[i-1]*p; for (int i=1;i<=n;++i) for (int j=0;j<l;++j) hash[i]+=(UL)s[i][j]*mi[l-j-1]; for (int j=0;j<l;++j) { Cnt.clear(); for (int i=1;i<=n;++i) { hash[i]-=(UL)s[i][j]*mi[l-j-1]; if (!Cnt[hash[i]]) ++Cnt[hash[i]]; else { int cnt=Cnt[hash[i]]; ans-=cnt*(cnt-1)/2; ++cnt; ans+=cnt*(cnt-1)/2; Cnt[hash[i]]=cnt; } hash[i]+=(UL)s[i][j]*mi[l-j-1]; } } PRintf("%d/n",ans);}

上一篇：Lua 环境在Linux上的安装

下一篇：212. Word Search II