【Nowcoder 上海五校赛】K序列

题目描述:

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

输入描述:

第一行为两个整数 n, K, 以空格分隔，第二行为 n 个整数，表示 a[1] ∼ a[n]，1 ≤ n ≤ 10⁵, 1 ≤ a[i] ≤ 10⁹, 1 ≤ nK ≤ 10⁷

输出描述:

输出一个整数表示最长子序列的长度 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);
}