• 【小奇模拟赛】小奇的自动机

    【小奇模拟赛】小奇的自动机

    【题目背景】小奇在研究后缀自动机时遇到了一个难题。【问题描述】定义:如果字符串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日995字典树,线段树
  • 【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日1,507贪心,字典树
  • 【bzoj1174】[Balkan2007]Toponyms

    【bzoj1174】[Balkan2007]Toponyms

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

    42014年4月2日1,494字典树
  • 【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日1,428字典树