首页 > 代码库 > BZOJ 1174: [Balkan2007]Toponyms

BZOJ 1174: [Balkan2007]Toponyms

二次联通门 : 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;
}

 

BZOJ 1174: [Balkan2007]Toponyms