首先,所有位置最多被染色一次,因为要染多次的话,还不如一开始就染成最终的颜色.并且你可以一开始就染好色
因为最终长度为2,那么如果染完后这个序列可以被折完,那么首先最多只有两种颜色,还有就是要满足对于所有同色极大联通块长度都要是偶数,不过第一个和最后一个长度可以为奇数
证明的话,先证充分条件,即这样子一定合法.可以搞出一个方法,每次只操作后面.先把最后面一个连通块长度缩成1(这样一定最优),然后因为接下来一个连通块长度为偶数,所以可以把接下来那个轴对称翻过去,然后重复这个操作直到长度为2.然后证中间有长度为奇数的一定不合法.首先如果缩到最后中间只有一个奇数长度的,那么你是翻不过去的.然后如果有多个奇数连通块,那么你怎么翻,中间部分都有奇数长度的.如果还是不理解可以问这个人(tpq)
然后考虑计算答案.首先长度为偶数的连通块可以拆成若干个长度为\(2\)的连通块,再根据第一个长度为\(2\)的连通块的起始位置是\(1\)还是\(2\)分类讨论,还有要使得染色次数最少,等价于不染色位置最多.枚举每一种颜色来算对应答案,如果连通块两个都是这种颜色,那么显然不用改;如果两个都不是这种颜色,那么都要染成另一种颜色,这种颜色是什么先不考虑;如果一个当前颜色一个不是当前颜色,那么可以发现把不是当前颜色的改成当前颜色一定不亏.现在再考虑另外一种颜色是什么,我们要尽量使得这种颜色位置最多,不过可能有些位置和当前枚举颜色在一起,这些位置要染掉,那么这种颜色的贡献就是出现总次数(\(记为cnt\))-和当前颜色在同一块的块个数(\(记为f_{i,j}\)).所以一种颜色答案\(i\)为\(n-cnt_i-\max_{j\neq i} (cnt_j-f_{i,j})\)
写的时候,\(f_{i,j}\)可以先把颜色不同的块内的两种颜色相互连边,然后\(f_{i,j}\)就是\(i,j\)之间的边数.然后按照\(cnt_j\)从大到小枚举另一种颜色,并且如果枚举到\(f_{i,j}=0\)的\(j\)就不用枚举了,接下来一定不优
#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define db double
using namespace std;
const int N=1e6+10;
int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
};
int n,m,a[N],cn[N],sq[N],an[N],f[N][2];
int v[N];
bool cmp(int aa,int bb){return cn[aa]>cn[bb];}
vector<int> e[N];
void wk()
{
for(int i=1;i<=m;++i)
{
vector<int>::iterator it;
for(it=e[i].begin();it!=e[i].end();++it)
++v[*it];
for(int j=1;j<=m;++j)
{
int x=sq[j];
if(i==x) continue;
an[i]=max(an[i],cn[i]+cn[x]-v[x]);
if(!v[x]) break;
}
for(it=e[i].begin();it!=e[i].end();++it)
--v[*it];
}
}
int main()
{
n=rd(),m=rd();
for(int i=1;i<=n;++i)
a[i]=rd(),++cn[a[i]];
for(int i=1;i<=m;++i)
an[i]=cn[i],sq[i]=i;
sort(sq+1,sq+m+1,cmp);
for(int i=1;i+1<=n;i+=2)
if(a[i]!=a[i+1])
e[a[i]].push_back(a[i+1]),e[a[i+1]].push_back(a[i]);
wk();
for(int i=1;i<=m;++i) e[i].clear();
for(int i=2;i+1<=n;i+=2)
if(a[i]!=a[i+1])
e[a[i]].push_back(a[i+1]),e[a[i+1]].push_back(a[i]);
wk();
for(int i=1;i<=m;++i) printf("%d\n",n-an[i]);
return 0;
}