题解：B4310 [蓝桥杯青少年组国赛 2024] 第五题

· · 题解

题目传送门

题意

找出和能被 k 整除的最长子串中起始位置最靠后的数列，输出它的长度和其中的每个数。

思路

题目还没看完，就眼前就自动浮现了三个字：前缀和。两个除以 k 余数相同的数相减一定能被 k 整除（就当余数抵消了吧）。这时，我们可以用 map 维护每一个余数第一次出现的位置（k 有点大，怕数组塞不下），如果出现了同样的余数并且长度大于等于 len（用来存储最终长度），就更新 len 的值。细节在代码中注释了。

代码

#include <bits/stdc++.h>
using namespace std;
int n, k, len = -1, l, r, sum, a[100010];
map<int, int> mp;
int main()
{
    scanf("%d%d", &n, &k);
    mp[0] = 0; //一定要把 mp[0] 初始化为 0，相当于从 1 开始选
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        sum = (sum + a[i]) % k;
        if (!mp.count(sum)) //如果没有这个键
            mp[sum] = i;
        else if (i - mp[sum] >= len)
            len = i - mp[sum], l = mp[sum] + 1, r = i;
    }
    printf("%d\n", len); //我的 len 初始化为 -1 了哈
    for (int i = l; i <= r && len != -1; i++) // 条件要加 len != -1
        printf("%d ", a[i]);
    return 0;
}

题解来之不易，且看且珍惜。给个赞再走吧。

题目传送门