P8663 [蓝桥杯 2018 省 A] 倍数问题 题解

· · 题解

有 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);
}