本文主要是介绍埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛 L-K序列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
给一个数组 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
注意:要开long long
代码1:
#include <iostream>
using namespace std;long long dis(long long a[], long long n, long long k)
{long long sum = 0;for (int i = 0; i < n; i++)sum += a[i];if (sum%k == 0) return n;for (int i = n - 1; i > 0; i--){sum = 0;for (int j = 0; j < i; j++)sum += a[j];if (sum % k == 0) return i;for (int h = 0; h < n - i; h++){sum = sum - a[h] + a[h+i];if (sum % k == 0) return i;}}return 0;
}int main()
{long long n, k,a[100005];while (cin >> n >> k){for (int i = 0; i < n; i++){cin >> a[i];}cout << dis(a, n, k) << endl;}return 0;
}
代码2:
#include <iostream>
#include <cmath>
using namespace std;
int main() {long long n,k;long long a[100005];while (cin >> n >> k){for (int i = 0; i < n; i++){cin >> a[i];}long long count = 0;for (int i = 0; i < n; i++){long long tmp = 0;for (int j = i; j < n; j++){tmp += a[j];if (tmp % k == 0)count = count > (j - i + 1) ? count : (j - i + 1);}if (count >= n - i)break;}cout << count << endl;return 0;}
}
这篇关于埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛 L-K序列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!