Current position : 首页 >> 字典树

  • 「小奇模拟赛」小奇的自动机

    「小奇模拟赛」小奇的自动机

    「题目背景」小奇在研究后缀自动机时遇到了一个难题。「问题描述」定义：如果字符串A是字符串B的后缀，那么称B是A的XQ串。小奇有n个只包含小写字母的字符串，编号为1-n，表示为Si。接下来对于每个串Si，小奇想知道：对于小奇拥有的n个字符串，所有是Si的XQ串的编号集合(包括i）中第Ki小的编号。「输入格式」第1行1个整数n。接下来n行，第i+1行包括1个字符串Si。再接下来n行，第n+1+i行的整数表示Ki。「输出格式」输出...

    02016年5月21日5,003字典树,线段树

  • 「BZOJ1954」Pku3764 The xor – longest Path

    「BZOJ1954」Pku3764 The xor - longest Path

    Description给定一棵n个点的带权树，求树上最长的异或和路径InputTheinputcontainsseveraltestcases.Thefirstlineofeachtestcasecontainsanintegern(1<=n<=100000),Thefollowingn-1lineseachcontainsthreeintegersu(0<=u<n),v(0<=v<n),w(0<=w<2^31),whichmeansthereisanedgebetweennodeuandvoflengthw.OutputForeachtestcaseoutputthexor-lengthofthexor-longestpath.SampleInput4123234246Samp...

    02014年12月16日4,706贪心,字典树

  • 「BZOJ1174」[Balkan2007] Toponyms

    「BZOJ1174」[Balkan2007] Toponyms

    Description给你一个字符集合,你从其中找出一些字符串出来.希望你找出来的这些字符串的最长公共前缀*字符串的总个数最大化.Input第一行给出数字N.N在[2,1000000]下面N行描述这些字符串,长度不超过20000总输入不超过20000字符Output asinglelinewithanintegerrepresentingthemaximallevelofcomplexity Lc(T).SampleInput7JoradeSusOrheiJoradeMijlocJoreniJoradeJosJapcaOrheiulVechiSampleOutput24题解首...

    42014年4月2日4,618字典树

  • 「POJ2001」Shortest Prefixes

    「POJ2001」Shortest Prefixes

    DescriptionAprefixofastringisasubstringstartingatthebeginningofthegivenstring.Theprefixesof"carbon"are:"c","ca","car","carb","carbo",and"carbon".Notethattheemptystringisnotconsideredaprefixinthisproblem,buteverynon-emptystringisconsideredtobeaprefixofitself.Ineverydaylanguage,wetendtoabbreviatewordsbyprefixes.Forexample,"carbohydrate"iscommonlyabbreviatedby"carb".Inthisproblem,givenasetofwo...

    02014年3月19日5,893字典树