1174: [Balkan2007]Toponyms

1174: [Balkan2007]Toponyms

题目链接

题目大意：有一个字符集合，从其中找一些字符串出来，最大化这些字符串的LCP长度*字符串个数

题解：稍有常识的人就能看出，这是一道Trie树裸题，在插入的时候顺手统计答案就可以了

然而这题卡空间，需要用邻接表存储

我的收获：……

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;int read() {int x = 0, f = 1; char c = getchar();while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }return x * f;
}#define maxn 5000010
#define LL long longint n, rt, ToT, m, val[maxn], head[maxn], nxt[maxn], to[maxn];
char ec[maxn];LL ans;
void insert() {int u = rt;val[u]++;char C = getchar();for(int i = 0; C != 'n'; i++, C = getchar()) {int v = -1;for(int e = head[u]; e; e = nxt[e])if(ec[e] == C){ v = to[e]; break; }if(v < 0) to[++m] = ++ToT, ec[m] = C, nxt[m] = head[u], head[u] = m, v = ToT;val[u = v]++;ans = max(ans, (LL)val[u] * (i + 1));}return ;
}int main() {n = read(); rt = ToT = 1;for(int i = 1; i <= n; i++) insert();printf("%lldn", ans);return 0;
}