每日一题冲刺大厂提高组第八天栗酱的数列

2022-10-10 86

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 大家好，我是泡泡，给大家带来每日一题的目的是为了更好的练习算法，我们的每日一题提高组是为了有余力的同学准备的，让大家练到各种各样的题目，一年以后，蜕变成为一个不一样的自己！

今日题目：栗酱的数列

题目描述

栗酱有一个长度为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;
}