今日题目:栗酱的数列
题目描述
栗酱有一个长度为n的数列A,一个长度为m的数列B,现在询问A中有多少个长度为m的连续子序列A',满足(a'1+b1)%k = (a'2+b2)%k = …… = (a'm + bm)%k。
输入描述:
第一行一个数T,表示有T组数据。
对于每组数据,
第一行三个整数,n, m, k。
第一行输入n个数, a1,a2,…,an, 表示A数列中的数,
第二行输入m个数, b1,b2,…,bm, 表示B数列中的数。
输出描述:
每一组数据输出一行,满足条件的连续子序列数量。
题目分析
题目难度:⭐️⭐️⭐️
题目涉及算法:kmp。
ps:有能力的小伙伴可以尝试优化自己的代码或者一题多解,这样能综合提升自己的算法能力
题解报告:
1.思路
这题考的是KMP,还是很明显的,大家根据题意来套板子就好了,什么?没有学过kmp?赶紧去学!
2.代码
#include<bits/stdc++.h> using namespace std; const int N = 200001; int a[N],b[N]; int main() { int t; cin>>t; while(t--) { int n,m,k; cin>>n>>m>>k; for(int i=0;i<n;i++) { cin>>a[i]; } for(int i=0;i<m;i++) { cin>>b[i]; } int sum=0; for(int i=0;i<=n-m;i++) { int z=0,flag=0; int num=(a[i]+b[z])%k; for(int j=i;j<i+m;j++) { if((a[j]+b[z])%k!=num) { flag=1; break; } z++; } if(!flag) { sum++; } } cout<<sum<<endl; } return 0; }