题解：P14796 [JOI 2026 二次预选] 究极团子达人 / Ultimate Dango Maker

· · 题解

原题传送门

题意

每三个元素 i,j,k 满足 |c_i-c_j|,|c_j-c_k|,|c_i-c_k|\le1 都会产生一组贡献，且每个元素只能产生一个贡献，求总贡献。

思路

明显，如果 i,j,k 能够产生贡献，它们的颜色数一定是相邻的两个。

具体来说，只能是 (c,c,c),(c,c,c+1),(c,c+1,c+1) 三种情况（c 是任意颜色但不是最大颜色）。

那么我们就想到了一个很好的贪心（凡是叫不出来的都是贪心）：先把 3 个颜色相同的团子串起来统计贡献，再对剩下的团子进行讨论。

具体来讲，对于所有 a_i(1\le i\le n)，先 a_i\gets a_i\bmod 3，在讨论相邻的颜色。

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 201000;

int n, a[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        ans += a[i] / 3, a[i] %= 3; // 同色讨论
    for (int i = 1; i <= n - 1; i++) {
        if (a[i] + a[i + 1] >= 3)
            ans++, a[i + 1] += a[i] - 3; // 相邻颜色的讨论，然后 a[i] 可以不清零，因为用不到了
    }
    printf("%lld", ans);
}

预计得分 42pts。

为什么？

让我们看看这个：

3
2 3 1

我们的代码会先把 a_2 处理掉，然后 a_1,a_3 就没用了，答案为 1。但是实际上应该是 (1,1,2),(2,2,1) 共两个（数字为颜色）。

这意味着我们的贪心假了……

反思一下，既然直接取模会破坏与两侧的联系，那么先把前面的处理掉再取模不就好了？

于是代码就有了。

AC Code（c++）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 201000;

int n, a[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    ll ans = 0;
    for (int i = 1; i <= n - 1; i++) {
        ans += a[i] / 3; // 此时取模不会对左侧产生影响，因为已经讨论过了，之后会再讨论右侧
        a[i] %= 3;
        if (a[i] + a[i + 1] >= 3)
            ans++, a[i + 1] += a[i] - 3; // 讨论
    }
    ans += a[n] / 3;
    a[n] %= 3; // a[n] 别忘了
    printf("%lld", ans);
}