二次联通门 : BZOJ 1174: [Balkan2007]Toponyms
权限题放题面
/* BZOJ 1174: [Balkan2007]Toponyms Trie树 将每个字符串插入Trie树中 定义Trie树上点的权值为 以当前点为根的子树中串的数量乘以当前点的深度 则答案即为最大的点权。。 不过这题卡空间
先用指针写了写,果然RE(就是超空间)
于是就改成前向星了
*/ #include <cstdio> void read (int &now) { register char word = getchar (); for (now = 0; word < '0' || word > '9'; word = getchar ()); for (; word >= '0' && word <= '9'; now = now * 10 + word - '0', word = getchar ()); } #define Max 5000010 int __next[Max]; int __to[Max]; int edge_list[Max]; int Edge_Count = 1; char __key[Max]; int value[Max]; inline int max (int a, int b) { return a > b ? a : b; } int main (int argc, char *argv[]) { int N; read (N); register char c; long long Answer = 0; int now, pos; for (register int i, j; N; -- N) { for (c = getchar (); c == '\n'; c = getchar ()); for (j = now = 1; c != '\n'; c = getchar (), j ++) { for (pos = 0, i = edge_list[now]; i; i = __next[i]) if (__key[i] == c) { pos = __to[i]; break; } if (!pos) { pos = ++ Edge_Count; __to[Edge_Count] = pos; __next[Edge_Count] = edge_list[now]; edge_list[now] = Edge_Count; __key[Edge_Count] = c; } value[now = pos] ++; Answer = max (Answer, (long long) j * value[now]); } } printf ("%d", Answer); return 0; }
指针:
#include <cstring> #include <cstdio> void read (int &now) { register char word = getchar (); for (now = 0; word < '0' || word > '9'; word = getchar ()); for (; word >= '0' && word <= '9'; now = now * 10 + word - '0', word = getchar ()); } #define Max 10000060 const int _L = 53; int Count; #define INF 1e7 bool visit[Max]; struct T_D { T_D *child[_L]; int Flandre; int number; T_D () { for (int i = 0; i < _L; i ++) this->child[i] = NULL; this->Flandre = 0; this->number = ++ Count; visit[Count] = true; } }; int value[Max]; int Answer = -INF; inline int max (int a, int b) { return a > b ? a : b; } class Trie_Type { private : T_D *Root; public : Trie_Type () { Root = new T_D; } void Insert (char *key) { T_D *now = Root; int Len = strlen (key), Id; -- Len; for (register int i = 0; i < Len; i ++) { Id = key[i] - '0'; if (!visit[now->number + 1]) now->child[Id] = new T_D; Answer = max (Answer, now->Flandre * i); now = now->child[Id]; } } }; Trie_Type Trie; char line[Max / 50]; int main (int argc, char *argv[]) { int N; read (N); for (; N; -- N) { gets (line); Trie.Insert (line); } printf ("%d", Answer); return 0; }