51nod 1526 分配笔名
2024-09-19 11:10:34
题目来源: CodeForces
基准时间限制:1 秒 空间限制:131072 KB 分值: 320 难度:7级算法题.
班里有n个同学。老师为他们选了n个笔名。现在要把这些笔名分配给每一个同学,每一个同学分配到一个笔名,每一个笔名必须分配给某个同学。现在定义笔名和真名之间的相关度是他们之间的最长公共前缀。设笔名为a,真名为b,则他们之间的相关度为lcp(a,b)。那么我们就可以得到匹配的质量是每一个同学笔名和真名之间相关度的和。
现在要求分配笔名,使得匹配质量最大。
样例解释:
· bill → bilbo (lcp = 3)
· galya → galadriel (lcp = 3)
· gennady → gendalf (lcp = 3)
· toshik → torin (lcp = 2)
· boris → smaug (lcp = 0)
Input
单组测试数据。
第一行有一个整数n (1≤n≤100000),表示班级中同学的数目。
接下来n行,表示每一个同学的真名,每一个名字是非空串,且由小写字母组成。
名字可能重复。
最后n行是老师已经安排好的笔名。每一个笔名是一个非空串,且由小写字母组成。
笔名可能重复。
输入的字符总数目不超过 800000。
Output
输出最大的匹配质量。
Input示例
样例输入1
5
gennady
galya
boris
bill
toshik
bilbo
torin
gendalf
smaug
galadriel
Output示例
样例输出1
11
System Message (题目提供者)
trie树乱搞
Rank2 实在没法优化了
#include <cstring>
#include <ctype.h>
#include <cstdio>
#define N 1000000
#define BUF 10000010
char real[N];
int ans,Answer,f[N],pos,len,cnt[N],n,trie[N][],exict[N],siz=;
char Buf[BUF],*buf=Buf;
inline void Read(int &x)
{
for(x=;!isdigit(*buf);++buf);
for(;isdigit(*buf);x=x*+*buf-'',++buf);
}
inline void Readch(char *c)
{
for(len=;!islower(*buf);++buf);
for(;islower(*buf);c[len++]=*buf,++buf);
}
inline void ins(int k,int &p)
{
if(!p) p=++siz;
cnt[p]++;
if(k+==len) return;
ins(k+,trie[p][real[k+]-'a']);
}
void query(int k,int p)
{
if(k==len||!p) return;
if(cnt[p]) ans++,cnt[p]--;
query(k+,trie[p][real[k+]-'a']);
}
inline void write(int now)
{
if(now>) write(now/);
putchar (now%+'');
}
int main()
{
fread(buf,,BUF,stdin);
Read(n);
for(int i=;i<=n;++i)
{
Readch(real);
ins(,trie[][real[]-'a']);
}
for(pos=;pos<=n;++pos)
{
Readch(real);
ans=;
query(,trie[][real[]-'a']);
Answer+=ans;
}
write(Answer);
return ;
}
最新文章
- 【三石jQuery视频教程】02.创建 FontAwesome 复选框和单选框
- AOP基础—代理模式
- 使用Java代码实现对宽带的连接
- WCF 部署在Windows 2012 IIS上各种报错的解决方法
- 一道java算法题分析
- HTML 5 Web 存储
- 不停止MySQL服务的情况下修改root的密码
- WPF点补间、拟合回归直线
- 【Oracle&;SQLServer】并集、交际、补集
- 段错误调试神器 - Core Dump详解
- 将less编译成css的gulp插件
- HTML之学习笔记(四)格式化标签和特殊字符
- UVALive 2522	Chocolate(概率DP)
- 使用Cookie记住用户名和密码
- BZOJ 1018: [SHOI2008]堵塞的交通traffic(线段树)
- 004_wireshark专题
- 给PHP开启shmop扩展实现共享内存
- 通过汇编一个简单的C程序,分析汇编代码理解计算机是如何工作的
- RabbitMQ入门:远程过程调用(RPC)
- hadoop MultipleInputs fails with ClassCastException (get fileName)