cdoj 1091-秋実兄貴の恋愛物語【kmp】
11045 ワード
http://acm.uestc.edu.cn/#/problem/show/1091
秋実兄貴の恋愛物語
Time Limit: 5000/2000MS (Java/Others) Memory Limit: 32000/32000KB (Java/Others)
Submit
Status
伝説にはこんな物語がある!
1ヶ月の白風清の夜、秋実の兄貴は彼の好きな妹を誘って一緒にキャンパスをぶらぶらして、ロマンチックな秋実の兄貴はその晩に妹に告白することにした.“XXXXX...”,秋実兄貴は長い間準備していたことを優しく話した.妹はロマンチックな方法で秋実の兄貴を受け入れることにした(実は妹はとっくに秋実の兄貴に心を動かして、この瞬間彼女はとっくに待ちきれなかったが、やはり秋実の兄貴の最後の関門を試験することにして、更に婉曲に受け入れる).妹は彼女の好きなハーモニカを取り出して、魅力的な曲を吹いて......「私の曲を繰り返してもらえますか?」しかし、万が一、秋実兄貴ができずに勝つ心を失ったことを考えると、妹は「私のメロディーの一部を吹くことができれば、約束します.これからは、私はあなたの一部です」と話した.
好奇心の強いあなたは、秋実さんが最終的に美人を抱いて帰ってきたかどうか本当に知りたいです.それ以外に、秋実さんが吹いた曲のメロディーが何回妹のメロディーに合っているか知りたいです.
2つの隣接する音符をつなぎ合わせると、妹が吹き出した音符は1本の折れ線Aを描くことができ、同様に、秋実兄貴が吹き出した音符も1本の折れ線Bを描くことができ、折れ線Bがすでに折れ線Aのある部分と完全に重なっているか、上下左右に平行移動して折れ線Aのある部分と完全に重なることができれば、秋実兄貴が妹のメロディーの一部を吹き出したことを示す.
Input
1行目は整数N(2≦N≦2 000,000)を入力し、妹がN個の音符を吹いたことを示す.
2行目にはN個の音符が入力され、各音符は整数であり、32ビットの整数の範囲内で、2つの音符ごとに1つのスペースで区切られている.
3行目は整数M(2≦M≦2 000,000)を入力し、秋実兄貴がM個の音符を吹いたことを示す.
最後の行にはM個の音符が入力され、各音符は整数であり、32ビットの整数の範囲内で、各2つの音符は1つのスペースで区切られている.
Output
秋実さんが美人を抱いて帰ったら、1行目は
秋実兄貴ができなかったら、
Sample input and output
Sample Input
Sample Output
解題構想:kmp.折れ線が重なると判断し、元のデータの隣接する点を減算することができ、kmpで子列の出現回数を直接求めることができるという.kmpについては、私のこのブログ:http://www.cnblogs.com/jiu0821/p/4189987.htmlを参考にすることができます.単求サブ列が初めて現れる位置は、next配列のnext[len]を使用する必要はありません.サブストリングの出現回数を求めるにはnext[len]を用いる必要があり,マッチングが完了するたびにjがlenに等しいことを意味し,この場合は第len項が一致しない(実際にはt列にはこれがない)と理解し,j=next[len]とし,次の出現状況を解き,最後に目的を達成する.
コード:
秋実兄貴の恋愛物語
Time Limit: 5000/2000MS (Java/Others) Memory Limit: 32000/32000KB (Java/Others)
Submit
Status
伝説にはこんな物語がある!
1ヶ月の白風清の夜、秋実の兄貴は彼の好きな妹を誘って一緒にキャンパスをぶらぶらして、ロマンチックな秋実の兄貴はその晩に妹に告白することにした.“XXXXX...”,秋実兄貴は長い間準備していたことを優しく話した.妹はロマンチックな方法で秋実の兄貴を受け入れることにした(実は妹はとっくに秋実の兄貴に心を動かして、この瞬間彼女はとっくに待ちきれなかったが、やはり秋実の兄貴の最後の関門を試験することにして、更に婉曲に受け入れる).妹は彼女の好きなハーモニカを取り出して、魅力的な曲を吹いて......「私の曲を繰り返してもらえますか?」しかし、万が一、秋実兄貴ができずに勝つ心を失ったことを考えると、妹は「私のメロディーの一部を吹くことができれば、約束します.これからは、私はあなたの一部です」と話した.
好奇心の強いあなたは、秋実さんが最終的に美人を抱いて帰ってきたかどうか本当に知りたいです.それ以外に、秋実さんが吹いた曲のメロディーが何回妹のメロディーに合っているか知りたいです.
2つの隣接する音符をつなぎ合わせると、妹が吹き出した音符は1本の折れ線Aを描くことができ、同様に、秋実兄貴が吹き出した音符も1本の折れ線Bを描くことができ、折れ線Bがすでに折れ線Aのある部分と完全に重なっているか、上下左右に平行移動して折れ線Aのある部分と完全に重なることができれば、秋実兄貴が妹のメロディーの一部を吹き出したことを示す.
Input
1行目は整数N(2≦N≦2 000,000)を入力し、妹がN個の音符を吹いたことを示す.
2行目にはN個の音符が入力され、各音符は整数であり、32ビットの整数の範囲内で、2つの音符ごとに1つのスペースで区切られている.
3行目は整数M(2≦M≦2 000,000)を入力し、秋実兄貴がM個の音符を吹いたことを示す.
最後の行にはM個の音符が入力され、各音符は整数であり、32ビットの整数の範囲内で、各2つの音符は1つのスペースで区切られている.
Output
秋実さんが美人を抱いて帰ったら、1行目は
Wow! Life Winner!、2行目はもう1つの整数を出力して、秋実さんの曲のメロディーが何回妹に合っているかを示します.秋実兄貴ができなかったら、
Oh. That's impossible. I must have had a dream.を出力します.Sample input and output
Sample Input
Sample Output
14
1 1 5 5 6 6 5 4 4 3 3 2 2 1
14
0 0 4 4 5 5 4 3 3 2 2 1 1 0Wow! Life Winner!
120
1 2 1 2 1 2 1 2 1 1 0 1 3 2 3 2 7 6 7 2
3
6 5 6Wow! Life Winner!
625
2 3 2 3 3 2 3 3 3 2 3 2 2 3 3 2 2 2 3 3 3 3 2 3 3
3
2 3 3Wow! Life Winner!
529
6 6 7 5 5 6 4 4 5 3 3 4 2 2 3 1 1 2 0 0 1 -1 -1 0 -2 -2 -1 -3 -3
8
6 6 7 5 5 6 4 4Wow! Life Winner!
826
1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0
5
1 1 0 1 1Oh. That's impossible. I must have had a dream.解題構想:kmp.折れ線が重なると判断し、元のデータの隣接する点を減算することができ、kmpで子列の出現回数を直接求めることができるという.kmpについては、私のこのブログ:http://www.cnblogs.com/jiu0821/p/4189987.htmlを参考にすることができます.単求サブ列が初めて現れる位置は、next配列のnext[len]を使用する必要はありません.サブストリングの出現回数を求めるにはnext[len]を用いる必要があり,マッチングが完了するたびにjがlenに等しいことを意味し,この場合は第len項が一致しない(実際にはt列にはこれがない)と理解し,j=next[len]とし,次の出現状況を解き,最後に目的を達成する.
コード:
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 using namespace std;
6
7 const int N=2000005;
8 int s[N],t[N];
9 int next_[N],len,ls;
10
11 void get_next_();
12 int kmp();
13
14 int main(){
15 //freopen("D:\\input.in","r",stdin);
16 scanf("%d%d",&ls,&s[0]);
17 for(int i=1;i<ls;i++) scanf("%d",&s[i]),s[i-1]=s[i]-s[i-1];
18 scanf("%d%d",&len,&t[0]);
19 for(int i=1;i<len;i++) scanf("%d",&t[i]),t[i-1]=t[i]-t[i-1];
20 ls--,len--;
21 get_next_();
22 int ans=kmp();
23 if(ans) printf("Wow! Life Winner!
%d
",ans);
24 else puts("Oh. That's impossible. I must have had a dream.");
25 return 0;
26 }
27 void get_next_(){
28 next_[0]=-1;
29 next_[1]=0;
30 for(int i=1;i<len;i++){
31 int j=next_[i];
32 while(1){
33 if(t[i]==t[j]){
34 next_[i+1]=j+1;
35 break;
36 }else{
37 j=next_[j];
38 }
39 if(j<0){
40 next_[i+1]=0;
41 break;
42 }
43 }
44 }
45 }
46 int kmp(){
47 int ans=0,i=0,j=0;
48 while(i<ls){
49 if(j<0||s[i]==t[j]) ++i,++j;
50 else j=next_[j];
51 if(j==len){
52 ans++;
53 j=next_[j];
54 }
55 }
56 return ans;
57 }