K序列最长子序列和%k==0_num++%k==0-CSDN博客

本文链接：https://blog.csdn.net/keepcoral/article/details/80139185

链接： https://www.nowcoder.com/acm/contest/91/L
来源：牛客网

空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

给一个数组 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

输出

这道题我以为是用dp去做，但好像dp有点难理解，我就去搜了别的题解，这份题解是这样的，我们把前序和%k求出来，然后把所有余数出现的位置找出来，用s1去标记最后一个出现的位置，用s2去标记第一个出现的位置，然后再去遍历一次s1,s2,因为我们是求出前序和的余数，那么我们只需要把s1[i]-s2[i]它们之间的余数就是0了，而s1[i],s2[i]代表的就是这两个子序列的最后一个位置的下标，那么这个就是k的倍数的子序列了，只需要找出其中最大的就可以了，注意一点，如果当出现%k==0时，我们没必要标记s2，因为我们直接要求的就是这个下标。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#define INF 99999999
using namespace std;
int s1[1000005];
int s2[1000005];
int main()
{
    int n,sum=0,temp,ans=0,i,j,k;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&temp);
        sum=(sum+temp)%k;//直接看余数就可以了
        s1[sum]=i;//标记最后一个数的位置
        if(!s2[sum]&&sum!=0)//标记第一个出现sum的位置
        {
            s2[sum]=i;
        }//如果sum==0没有必要去标记
        //因为我们需要求的就直接是%k余数是0的
    }
    for(i=0;i<=k-1;i++)
    {
        ans=max(ans,s1[i]-s2[i]);
        //只要将余数相等的两个位置一相减就是说所求的最长子序列
        
    }
    printf("%d\n",ans);
}