自动搬运

查看原文

来自洛谷，原作者为

	5k_sync_closer 数据结构真可爱。

搬运于2025-08-24 22:41:12，当前版本为作者最后更新于2023-06-17 15:26:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

有 $a+b+c\equiv 0\pmod k$，则 $a\bmod k+b\bmod k+c\bmod k\in\{0,k,2k\}$。

证明比较显然，小于 $3k$ 的 $k$ 的倍数只有 $\{0,k,2k\}$。

分讨三种情况，对 $a\bmod k+b\bmod k+c\bmod k=z$ 的情况枚举 $a\bmod k,b\bmod k$，则 $c\bmod k=z-a\bmod k-b\bmod k$，

然后可以得到 $a\bmod k,b\bmod k,c\bmod k$ 的值，取同余类中最大值即可，注意重复情况。

复杂度 $O(n+k^2)$。

#include <cstdio>
#include <algorithm>
using namespace std;
int n, k, q, f[1050][3];
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < k; ++i)
        f[i][0] = f[i][1] = f[i][2] = -6e8;
    for (int i = 1, x, y; i <= n; ++i)
    {
        scanf("%d", &x);
        if (f[y = x % k][0] < x)
            f[y][2] = f[y][1], f[y][1] = f[y][0], f[y][0] = x;
        else if (f[y][1] < x)
            f[y][2] = f[y][1], f[y][1] = x;
        else if (f[y][2] < x)
            f[y][2] = x;
    }
    for (int z = 0; z <= k << 1; z += k)
        for (int i = 0; i < k; ++i)
            for (int j = 0, p; j < k; ++j)
                if ((p = z - i - j) >= 0 && p < k)
                    q = max(q, f[i][0] + f[j][i == j] + f[z - i - j][(i == p) + (j == p)]);
    return !printf("%d", q);
}