欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【Nowcoder 上海五校赛】K序列

程序员文章站 2022-09-28 07:58:48
题目描述: 给一个数组 a,长度为 n,若某个子序列中的和为 K 的倍数,那么这个序列被称为“K 序列”。现在要你 对数组 a 求出最长的子序列的长度,满足这个序列是 K 序列。 输入描述: 第一行为两个整数 n, K, 以空格分隔,第二行为 n 个整数,表示 a[1] ∼ a[n],1 ≤ n ≤ ......

题目描述:

给一个数组 a,长度为 n,若某个子序列中的和为 K 的倍数,那么这个序列被称为“K 序列”。现在要你 对数组 a 求出最长的子序列的长度,满足这个序列是 K 序列。 

输入描述:

第一行为两个整数 n, K, 以空格分隔,第二行为 n 个整数,表示 a[1] ∼ a[n],1 ≤ n ≤ 105, 1 ≤ a[i] ≤ 109, 1 ≤ nK ≤ 107

输出描述:

输出一个整数表示最长子序列的长度 m

[示例1]

输入

7 5
10 3 4 2 2 9 8

输出

6

题解

① 把序列中每一个数相加,再mod k,将得到的值作为数组下标,序列中的位置作为数组的值

② 开两个数组s1,s2:

s1数组存每次更新的位置,s2数组存第一次更新的位置,切记s2[0]的值恒为0

③ 最后取s1和s2每个对应位置 差的最大值

#include<bits/stdc++.h>
#define N 100005 
using namespace std;
int s1[N],s2[N];
int main()
{
    int n,k,i,a,maxx=0,s=0;
    cin>>n>>k;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a);
        s=(s+a)%k;       //和的mod
        s1[s]=i;         //s1存每次更新的位置
        if(!s2[s]&&s)    //s2存第一次更新的位置
            s2[s]=i;
    }
    for(i=0;i<k;i++)
        if(s1[i]-s2[i]>maxx)
            maxx=s1[i]-s2[i];

    printf("%d",maxx);
}