欢迎来到天天文库
浏览记录
ID:14522674
大小:52.00 KB
页数:7页
时间:2018-07-29
《pku1743 musical theme详细解题报告后缀数组求不重叠的最长重复子串》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、Pku1743MusicalTheme/*Name:pku1743Copyright:ecjtu_acmAuthor:yimaoDate:16/02/1113:35Description:二分答案,后缀数组求不重叠的最长重复子串*/一、题目DescriptionAmusicalmelodyisrepresentedasasequenceofN(1<=N<=20000)notesthatareintegersintherange1..88,eachrepresentingakeyonthepiano.Itisunf
2、ortunatebuttruethatthisrepresentationofmelodiesignoresthenotionofmusicaltiming;but,thisprogrammingtaskisaboutnotesandnottimings.Manycomposersstructuretheirmusicaroundarepeating&qout;theme&qout;,which,beingasubsequenceofanentiremelody,isasequenceofintegersinou
3、rrepresentation.Asubsequenceofamelodyisathemeifit:·isatleastfivenoteslong·appears(potentiallytransposed--seebelow)againsomewhereelseinthepieceofmusic·isdisjointfrom(i.e.,non-overlappingwith)atleastoneofitsotherappearance(s)Transposedmeansthataconstantpositive
4、ornegativevalueisaddedtoeverynotevalueinthethemesubsequence.Givenamelody,computethelength(numberofnotes)ofthelongesttheme.Onesecondtimelimitforthisproblem'ssolutions!InputTheinputcontainsseveraltestcases.ThefirstlineofeachtestcasecontainstheintegerN.Thefollow
5、ingnintegersrepresentthesequenceofnotes.Thelasttestcaseisfollowedbyonezero.OutputForeachtestcase,theoutputfileshouldcontainasinglelinewithasingleintegerthatrepresentsthelengthofthelongesttheme.Iftherearenothemes,output0.SampleInput3025273034394552606979696052
6、45393430262218827874706667646065800SampleOutput5HintUsescanfinsteadofcintoreducethereadtime.SourceLouTiancheng@POJ二、题目大意及分析【前话】我的poj第200题;楼教主男人八题之一;3xian在status里以绝对的时空优势排第一;纪念我的百度空间访问量破2000;我的第一道后缀数组题;典型的二分答案,用后缀数组求不重叠的最长重复子串;网上看题解不下10篇,综合之后才知道他们大概在说些什么,感叹前人栽
7、树,后人乘凉;可以证明本篇文章应该是字数最多的pku1743题解了;【题意】给定一个正整数N(N<=20000),然后是N个整数xi,(1<=xi<=88,1<=i<=N)组成一个有序的整数序列;问这个序列中存在的最长一个符合条件的子序列长度是多少,符合的条件是1、子序列A长度至少为5;2、有另外一个子序列B,且A、B二者没有相交部分(即不存在xi同时在A,B里出现,这里针对下标而言,A,B的元素在整个序列里下标都不一样);3、A,B的长度一样,设x[i],…x[i+k],x[j],…x[j+k],那么要求(x[
8、j]-x[i])=(x[j+1]-x[i+1])=…=(x[i+k],x[j+k]);即按下标对应的元素差值要相等,差值可以是0,1,2,-1,-2……;当然,为了满足2,(i+k)=4;举例说明:例1:135357答案是3,(对应差值是2,如果是35和35对应,则长度是2,求的是存在的最长长度)例2:12341234答案是4,(对
此文档下载收益归作者所有