bzoj3555 [Ctsc2014]企鹅QQ——字符串哈希
2024-08-31 01:16:51
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3555
很久以前就讲过哈希,但一直没写过题,所以这是哈希第一题!
哈希就是把一个字符串映射成一个数,竟然还能排序!
参考了 hzwer 的博客,但为什么写出来比别人慢了一倍...
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int const maxn=,maxm=;
int n,m,tp,ans;
ll f[maxn][maxm],g[maxn][maxm],tmp[maxn];//ll
char ch[maxm];
void init(int x)
{
for(int i=;i<=m;i++)f[x][i]=f[x][i-]*+ch[i];
for(int i=m;i;i--)g[x][i]=g[x][i+]*+ch[i];
}
int main()
{
scanf("%d%d%d",&n,&m,&tp);
for(int i=;i<=n;i++){cin>>ch+; init(i);}
for(int j=;j<=m;j++)//枚举每一位
{
for(int i=;i<=n;i++)//除这一位的每一个字符串
tmp[i]=f[i][j-]*+g[i][j+]*;
sort(tmp+,tmp+n+);
for(int i=,nw=;i<=n;i++)
{
if(tmp[i]==tmp[i-])ans+=nw,nw++;
else nw=;
}
}
printf("%d\n",ans);
return ;
}
最新文章
- 基于keepalived双主模型的高可用LVS
- python爬虫小项目实战
- ZBrush该如何通过结合KeyShot制作逼真玉佩
- 一次性下载CVPR2016的所有文章
- iTool拷贝app到电脑上
- OllyDBG 1.10
- So easy Webservice 4.Java方式访问WebService(使用jdk1.6以上 wsimport命令)
- Akka学习博客
- CentOS 6.6 FTP install
- ecshop--加载初始化文件
- css 一些事
- 算法模板——KMP字符串匹配
- 使用xorm工具,根据数据库自动生成 go 代码
- 【ASP.NET MVC系列】数据验证和注解
- 迭代DOM集合的几种方法
- Docker 从入门到实践(二)Docker 三个基本概念
- 为什么java实体类需要重写toString方法
- Codeforces 954C Matrix Walk (思维)
- VOIP NAT穿越之SIP信令穿越
- 关于gridview改变行内容事件需要点击别的行或控件才能执行