hd1711Number Sequence
这篇排版有问题,不过试了几次都改不来也就这样吧
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description Given two sequences of numbers : a[1], a[2], …… , a[N], and b[1], b[2], …… , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2], …… , a[K + M – 1] = b[M]. If there are more than one K exist, output the smallest one.
Input The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], …… , a[N]. The third line contains M integers which indicate b[1], b[2], …… , b[M]. All integers are in the range of [-1000000, 1000000].
Output For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.
Sample Input
2 13 5 1 2 1 2 3 1 2 3 1 3 2 1 2 1 2 3 1 3 13 5 1 2 1 2 3 1 2 3 1 3 2 1 2 1 2 3 2 1
Sample Output 6 -1 做题思路:给出一个主序列,和一个匹配序列,如果能够匹配,则输出匹配序列第一个数在主序列中的位置. 这道题是kmp的基础题.
开始输入啥都没问题,然后就是通不过,说什么时间超限,最后改过了改过去,才发现,用的是cin输入输出流,这个在算法竞赛那本紫书中也提到了,以后注意,然后尽量改掉用万能有文件的习惯,有的编译器,不支持。
Cyclic Nacklace Problem Description As Christmas is around the corner, Boys are busy in choosing christmas presents to send to their girlfriends. It is believed that chain bracelet is a good choice. However, Things are not always so simple, as is known to everyone, girl’s fond of the colorful decoration to make bracelet appears vivid and lively, meanwhile they want to display their mature side as college students. after CC understands the girls demands, he intends to sell the chain bracelet called CharmBracelet. The CharmBracelet is made up with colorful pearls to show girls’ lively, and the most important thing is that it must be connected by a cyclic chain which means the color of pearls are cyclic connected from the left to right. And the cyclic count must be more than one. If you connect the leftmost pearl and the rightmost pearl of such chain, you can make a CharmBracelet. Just like the pictrue below, this CharmBracelet’s cycle is 9 and its cyclic count is 2: Now CC has brought in some ordinary bracelet chains, he wants to buy minimum number of pearls to make CharmBracelets so that he can save more money. but when remaking the bracelet, he can only add color pearls to the left end and right end of the chain, that is to say, adding to the middle is forbidden. Input Output Sample Input Sample Output [题目大意:求再加几个,才能构成循环] 【题解】【kmp】 【kmp,利用失配函数,求出最小循环节(最小循环节=原串长度-末位失配),首先判断循环节是否为0,若为0,直接输出原串长度;然后看原串是否能被循环节整除,若能,则输出0,;若不能,则求出还有几位没有循环,输出】
|
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114892.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...