埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛 L K序列

Description:

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

Input:

第一行为两个整数 n, K, 以空格分隔，第二行为 $n$n 个整数，表示 $a\left[1\right],\dots ,a\left[n\right]，1\le n\le 10^5,1\le a\left[i\right]\le 10^9,1\le nK\le 10^7$a[1],…,a[n]，1≤n≤105,1≤a[i]≤109,1≤nK≤107

Output:

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

Sample Input:

7 5
10 3 4 2 2 9 8

Sample Output:

6

题目链接

这道题目是一道动态规划题，但是数据好像可以直接暴力，然后稍微去除一点多余枚举就能A。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6+5;
const double eps = 1e-5;
const double e = 2.718281828459;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int a[maxn];
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int len = 0, maxlen = 0;
    for (int i = 0; i < n; ++i) {
        if ((n - i) < maxlen) {
            break;
        }
        ll sum = 0;
        for (int j = i; j < n; ++j) {
            sum += a[j];
            if (sum % k == 0) {
                len = j - i + 1;
            }
            if (len > maxlen) {
                maxlen = len;
            }
        }
    }
    cout << maxlen;
    return 0;
}