【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); }
上一篇: 从零开始学MySQL(三)
下一篇: 微信朋友圈营销的新尝试