题解：P5101 [JOI 2017 Final] 绳 / Rope

· · 题解

更好的阅读体验

把一叠线染成相同颜色的代价是这叠线的厚度。这意味着如果这叠线当中有和你要染的颜色相同的线，也会付出不必要的代价，一定不优。

我们猜想能折成一个长度为 2 的段的充要条件，是：

  1. 原绳子中只有两种颜色。
  2. 除了开头和结尾，每个同色连续段的长度都为偶数。

结论 1 显然正确。因为最后只有两种颜色。

考虑结论 2 的充分性：有图有真相。

考虑最左边的一段，我们可以每次折长度为 1 的一小段。这样若干次操作之后这一段长度可以变成 1。

由于红色段后的蓝色段长度是偶数，所以一定可以把蓝色段对折。这样成为了另外一个子问题。

即使蓝色段对折后长度变成了奇数，但是别忘了，这时的蓝色段变成最左边的段了。所以可以同样进行操作使蓝色段长度为 1。

由此我们证明了该结论的充分性。

必要性比较显然。在中间的一段长度为奇数的段，永远不可能由对折删去。

我们会发现，满足这两个条件后，无非就是两种情况：

只讲第一种情况。

我们枚举两种颜色 i, j，假设初始时出现次数分别为 cnt_i, cnt_j。那么只考虑第一个条件，那就要将所有颜色 \not = i 或 j 的位置全部改成 i 或 j，耗费 n - cnt_i - cnt_j 的代价。假设 f_{i, j} 表示同时包含 i, j 颜色的段的数量。那么如果一个段同时包含颜色 i, j，由条件 2 我们知道这是不合法的。所以我们还要花费 f_{i, j} 的代价调整到合法状态。

所以 ans_i = \max \limits_{j \not = i} (n - cnt_i - cnt_j + f_{i, j}) = n - cnt_i - \min \limits_{j \not = i}(cnt_j - f_{i, j})。

然后我们注意到对于一个 i，所有 f_{i, j} 之和至多等于包含颜色 i 的段的数量乘以一个常数。所以对于所有 i, j，满足 f_{i, j} 非零的二元组 (i ,j) 只有总共 O(n) 对。

所以我们可以用一个大根堆，堆里存的是所有 cnt_j。对于一个 j，我们把 i 取出来，再把 f_{i, j} \not = 0 的 j 取出来单独处理。然后剩余部分直接取堆顶即可。

对两种情况分别做，取 \max 就可以了。

那么这道题就做完了，复杂度 O(n \log n)。

#include<bits/stdc++.h>
#define endl '\n'
#define N 1000006
using namespace std;
int n,m,a[N],cnt[N],f[N],del[N],ans[N];
vector<pair<int,int> > vec[N];
priority_queue<pair<int,int> > q;
void solve(int st)
{
    while(q.size())q.pop();
    for(int i=1;i<=m;i++)vec[i].clear();
    for(int i=st;i<=n;i+=2)
    {
        if(i!=n)
        {
            vec[a[i]].push_back({i,i+1});
            if(a[i]!=a[i+1])vec[a[i+1]].push_back({i+1,i});
        } else vec[a[i]].push_back({i,i});
    }
    if(st>1)vec[a[1]].push_back({1,1});
    for(int i=1;i<=m;i++)q.push({cnt[i],i});
    for(int i=1;i<=m;i++)
    {
        int maxn=0;
        vector<int> col;
        for(auto [x,y]:vec[i])
            if(a[y]!=i)f[a[y]]++,col.push_back(a[y]);
        for(int j:col)maxn=max(maxn,cnt[j]-f[j]),del[j]=1;
        del[i]=1;
        vector<pair<int,int> > change;
        while(q.size())
        {
            auto [x,y]=q.top();
            if(del[y])change.push_back({x,y}),q.pop();
            else break;
        }
        if(q.size())maxn=max(maxn,q.top().first);
        ans[i]=min(ans[i],n-cnt[i]-maxn);
        for(int j:col)del[j]=0,f[j]=0;
        del[i]=0;
        for(auto [x,y]:change)q.push({x,y});
    }
}
main()
{
    scanf("%d%d",&n,&m);
    memset(ans,0x3f,sizeof(ans));
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),cnt[a[i]]++;
    solve(1),solve(2);
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}