[SCP-J 2026] 染色 / color 题解

Foreverchan · 2026-10-18 19:25:08 · 题解

数据提供者 && 验题人 题解

讲个笑话，WsW 的数据，造的时候全是错的，我给连夜擦的鼙鼓。

实战好像很多人没考虑全情况变成了 92/88/80 分。

验题人题解

考虑一共 5 种情况是有意义的：

1. 全是红的或者全是蓝的（n\le 2）。
2. 开头一个红，后面全蓝。
3. 结尾一个蓝，前面全红。
4. 前半段是蓝，后半段是红。

前四种都可以直接扫一遍，第五种前缀最小值。

我把五种做法没写的全卡了一个遍，按照遗漏的东西的多少，获得 72-92 分（第 5 种最复杂，卡的最多），全写的 100 分。

当然，有更简单且更好写的总结做法，下面给出一个 AI generate 的。

::::success[C++17]

#include<bits/stdc++.h>
using namespace std;
const int maxn=2000000+5;
int a[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int ans=0,ans2=0;
    if(n==2)
    {
        ans=max(0,a[n]-a[1]);//1
        printf("%d\n",ans);
        return 0;
    }
    int mn=a[2];
    for(int i=2;i<n;i++)
    {
        mn=min(a[i],mn);
        ans=max(a[i]-mn,ans);//5 
        ans2=max(a[i]-a[i+1],ans2);//4 
    }
    int res=-2147483647;
    res=max(res,a[n]-a[2]);//2
    res=max(res,a[n-1]-a[1]);//3
    res=max(res,a[n]-a[1]+ans2);//4
    res=max(res,a[n]-a[1]+ans);//5
    printf("%d\n",res);
    return 0;
}

::::

以下做法来自 AI（数据的对拍器用的是这个）:

枚举数组首尾（位置 1 和位置 n）的颜色关系，可以得到最终答案的封闭形式：

同色的中间元素全部抵消，只留首尾 A_n-A_1；

异色时，为了最大化收益，只需要考虑一个分界点，所以只需要看相邻差值 \max_{1\le k\le n}(A_k-A_{k+1})；

中间任意两个点产生的额外收益，\max_{1\le i\le j\le n}(A_j-A_i)，只要维护前缀最小值，即可解决。时间复杂度 O(n)。

若不会维护，可以 O(n^2) 的部分暴力，然后省略此步或者进行一些贪心，根据实现能得 72-88 分。

::::success[C++17（对拍用）]

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    long long base = a[n - 1] - a[0];

    // 1. 相邻最大下降值 (A_k - A_{k+1})
    long long max_adj = LLONG_MIN;
    for (int i = 0; i + 1 < n; i++) {
        max_adj = max(max_adj, a[i] - a[i + 1]);
    }

    // 2. 中间任意两点最大正向差 (1 < i < j < n)
    long long max_mid = 0;          // 至少为 0（取 i = j）
    long long min_pref = LLONG_MAX; // 前缀最小值（从下标 1 开始）
    for (int j = 2; j < n - 1; j++) { // j 从 2 到 n-2 (0-index)
        min_pref = min(min_pref, a[j - 1]);
        max_mid = max(max_mid, a[j] - min_pref);
    }

    long long extra = max({0LL, max_adj, max_mid});
    cout << base + extra << '\n';

    return 0;
}

::::