我是靠谱客的博主 大意山水,这篇文章主要介绍hdu 5918 Harmonic Value Description 2016ACM/CCPC长春赛区现场赛H,现在分享给大家,希望可以做个参考。

Problem Description
Mr. Frog has two sequences  a1,a2,,an  and  b1,b2,,bm  and a number p. He wants to know the number of positions q such that sequence  b1,b2,,bm  is exactly the sequence  aq,aq+p,aq+2p,,aq+(m1)p  where  q+(m1)pn  and  q1 .
 

Input
The first line contains only one integer  T100 , which indicates the number of test cases.

Each test case contains three lines.

The first line contains three space-separated integers  1n106,1m106  and  1p106 .

The second line contains n integers  a1,a2,,an(1ai109) .

the third line contains m integers  b1,b2,,bm(1bi109) .
 

Output
For each test case, output one line “Case #x: y”, where x is the case number (starting from 1) and y is the number of valid q’s.
 

Sample Input
复制代码
1
2
3
4
5
6
7
8
9
10
11
2 6 3 1 1 2 3 1 2 3 1 2 3 6 3 2 1 3 2 2 3 1 1 2 3
 

Sample Output
复制代码
1
2
3
4
5
6
Case #1: 2 Case #2: 1


将a数列的元素按照对p取模的值重新排列,构成新的数列,不同取模值之间加上一个-1作为分界

然后直接跑KMP即可

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<cstdio> #include<string> #include<cstring> using namespace std; int a[200001],aa[100001],b[100001]; int loc[100001],net[100001]; int n,m; inline void KMP() { int i,j; for(i=1;i<m;i++) { j=i; while(j>0) { j=net[j]; if(b[j]==b[i]) { net[i+1]=j+1; break; } } } for(i=0,j=0;i<n;i++) { if(j<m&&a[i]==b[j]) j++; else { while(j>0) { j=net[j]; if(a[i]==b[j]) { j++; break; } } } if(j==m) { loc[0]++; loc[loc[0]]=(i-m+1)+1; } } } int main() { int T,k=0; scanf("%d",&T); while(T>0) { T--; k++; int p; scanf("%d%d%d",&n,&m,&p); int i,j; for(i=0;i<n;i++) scanf("%d",&aa[i]); for(i=0;i<m;i++) scanf("%d",&b[i]); int tot=-1; for(i=0;i<p;i++) { for(j=i;j<n;j+=p) { tot++; a[tot]=aa[j]; } tot++; a[tot]=-1; } // for(i=0;i<=tot;i++) // printf("%d ",a[i]); // printf("n"); memset(net,0,sizeof(net)); loc[0]=0; n=tot+1; KMP(); printf("Case #%d: %dn",k,loc[0]); } return 0; }


最后

以上就是大意山水最近收集整理的关于hdu 5918 Harmonic Value Description 2016ACM/CCPC长春赛区现场赛H的全部内容,更多相关hdu内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(83)

评论列表共有 0 条评论

立即
投稿
返回
顶部