CF1615G Maximum Adjacent Pairs

\(CF1615G\)

Description

给定一个数列 \(a\)，你需要将所有 \(a_i=0\) 的位置填上一个 \(1\sim n\) 的正整数，使得数列的「值」最大。

数列的值定义为满足以下条件的 \(k\) 的个数：

• 存在 \(i\in\Z[1,n-1]*i*∈Z[1,*n*?1]\)，使得 \(a_{i}=a_{i+1}=k\)。

输出值最大的序列，若有多解，输出任意一个。

\(0\le a\le \min(n,600)\)；\(0

Solution

转化到匹配问题是比较直觉的？

一开始的错误思路是直接对于每个数匹配位置，会出现这种情况

\(01000020\)，直接匹配的话可能会出现，\(01100220\)，最优匹配显然是\(11000022\)

那么考虑我们初始状态是一段连续的非\(0\)和\(0\)拼接而成，我们考虑进行连续段匹配

比较显然的几个结论

长度为偶数的 \(0\) 段，两边都匹配或者两边都不匹配，是肯定不劣的

长度为奇数的 \(0\) 段，只有一边匹配或者不匹配，也是不劣的

那么对于这个模型建图：

长度偶数段：左右端点连边，左右边界分别和左右端点连边

长度奇数段：左右边界和区间连边

跑一遍最大匹配就好了，由于是一般图，带花树(复杂度稳定过不去)\(/\)随机匈牙利(直接踩过去)

#define Eternal_Battle ZXK
#include
#define MAXN 300005
using namespace std;
int match[MAXN],vis[MAXN],a[MAXN],Lim=600,Tim,n;
mt19937 my_rd(time(0));
vectorrd[MAXN];
mappy[605];
bool No[MAXN];
void add(int u,int v)
{
	 if(No[u]||No[v]) return ;
	 rd[u].push_back(v);
	 rd[v].push_back(u);
}
bool dfs(int now)
{
	 shuffle(rd[now].begin(),rd[now].end(),my_rd);
	 vis[now]=Tim;
	 for(int i=0;i