【题解】CF1479B1 Painting the Array I

· · 题解

题意简述

定义连续段 seg(c)：将序列 c 中的相邻的相同元素合并后的长度。

给定长度为 n 的序列 a_1,a_2,\cdots,a_n，要求将其分成两个不相交的子序列 a^{(0)} 和 a^{(1)}，使得 seg(a^{(0)})+seg(a^{(1)}) 最大，求这个最大值。（也可理解为给第 i 个元素涂上颜色 b_i，其中 b_i=0 或 b_i=1，然后将颜色为 0 和颜色为 1 的元素分别从左到右取出）

数据范围：n \le 10^5，1 \le a_i \le n

分析 + 题解

题目可以看作有两个队列 s 和 t，从左到右依次选择每个元素是加入 s 队尾，还是加入 t 队尾，使得最后 seg(s)+seg(t) 最大。

设当前 s 队尾元素为 x，t 队尾元素为 y，要加入的元素为 z（为了方便，一开始 x=y=0），我们给出下列贪心策略：

  1. 若 z 与 x,y 中的至少一个相等，我们将 z 加入当前队尾不为 z 的队列。（若 z=x=y，可任意选择）

  2. 若 z 不与 x,y 中的任意一个相等，我们将 z 加入 s 当且仅当 next(x)<next(y)。其中 next(x) 表示 x 这种值下一次出现的位置，若之后没有出现 next(x)=n+1。

感性理解：

  1. 如果不这样做的话，那之后一次对于相等的 z 这样做，答案相同，效果等价；（效果指操作后 x=y=z）若之后一次都没有对相等的 z 这样做，答案减少 1；

  2. 为了让 x 和 a_{next(x)} 不要连成一段，用与它们都不同的 z 隔开，而 y 和 a_{next(y)} 之后更有可能被其他元素隔开。

理性证明：

分类讨论即可发现这样的策略不会比其他的答案差，比较冗长，此处略。（可以看一下官方题解的证明，建议看 "An Intutive Proof"，更加直观）

代码

预处理 Next 数组然后模拟即可。

#include<bits/stdc++.h>
using namespace std;
const int max_n=1e5+5;
int a[max_n],id[max_n],Next[max_n];
typedef pair<int,int> P;//前一个是元素的值，后一个是元素的编号
vector<P> w,b;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",a+i);
        id[i]=n+1;//注意初始化
    }
    for(int i=n;i>=1;--i)
    {
        Next[i]=id[a[i]];
        id[a[i]]=i;
    }
    w.push_back(P(0,n+1));
    b.push_back(P(0,n+1));
    int ans=0;
    for(int i=1;i<=n;++i)
    {
        if(a[i]==w.back().first)
        {
            if(a[i]!=b.back().first)
                ++ans;
            b.push_back(P(a[i],Next[i]));
        }
        else if(a[i]==b.back().first)
        {
            ++ans;
            w.push_back(P(a[i],Next[i]));
        }
        else
        {
            ++ans;
            if(w.back().second<b.back().second)
                w.push_back(P(a[i],Next[i]));
            else
                b.push_back(P(a[i],Next[i]));
        }
    }
    printf("%d\n",ans);
    return 0;
}