题解 BZOJ 1174 [Balkan2007]Toponyms

给你一个字符集合,你从其中找出一些字符串出来. 希望你找出来的这些字符串的最长公共前缀*字符串的总个数最大化.
这个问题很简单吧..用trie随便搞一搞。
但是Input是这么写的:
第一行给出数字N.N在[2,1000000] 下面N行描述这些字符串,长度不超过20000 。总字符不超过20000。

1000000个串怎么会总字符不超过20000。
gmh神犇告诉我这题有70多个RE..
然后Google了原题。
发现是保证输入文件<=10MB

就是串长最长能到$10^7$级别。。
字母有大小写好像trie树爆空间。。就写了hash.
听说写压缩路径的字典树也行……
ps.已发邮件给bz,已改题面。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
using namespace std;
int n;
int H[1048576],X[8000000],num[8000000];
unsigned long long P[8000000];
int tot;
char s[20005];
long long ans;
void add(int x,unsigned long long y){
P[++tot]=y;X[tot]=H[x];H[x]=tot;num[tot]=1;
}
const int SIZE=0xFFFFF;
inline void insert(unsigned long long has,int l){
bool ok=0;
int p=has&SIZE;
for(int i=H[p];i;i=X[i]){
if(P[i]==has){
ok=1;
num[i]++;
ans=max(ans,num[i]*1LL*(l+1));
}
}
if(!ok){
add(p,has);
ans=max(ans,l+1LL);
}
}
int main(){
scanf("%d\n",&n);
for(int i=1;i<=n;i++){
gets(s);
unsigned long long h=0;
for(int j=0;s[j];j++){
h=(h<<8)+(h<<2)+h+s[j];
insert(h,j);
}
}
printf("%lld\n",ans);
return 0;
}
评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框