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<n\le 3\times 10^5\)

Solution

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

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

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

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

比较显然的几个结论

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

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

那么对于这个模型建图：

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

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

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

#define Eternal_Battle ZXK

#include<bits/stdc++.h>

#define MAXN 300005

using namespace std;

int match[MAXN],vis[MAXN],a[MAXN],Lim=600,Tim,n;

mt19937 my_rd(time(0));

vector<int>rd[MAXN];

map<int,int>py[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<rd[now].size();i++)

	 {

	 	 int y=rd[now][i];

	 	 if(vis[match[y]]==Tim) continue;

	 	 int z=match[y];

	 	 match[now]=y;

	 	 match[y]=now;

	 	 match[z]=0;

	 	 if(!z||dfs(z)) return true;

	 	 match[now]=0;

	 	 match[y]=z;

	 	 match[z]=y;

	 }

	 return false;

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%d",&a[i]);

	for(int i=1;i<n;i++)

	{

		if(a[i]==a[i+1]) No[a[i]]=true;

	}

	No[0]=true;

	for(int i=1,j=0;i<=n;i++)

	{

		if(a[i])

		{

		   if(j+1==i) goto EB;

		   else if((i-j)%2==1)

		   {

		   	    Lim++;

		   	    add(a[j],Lim);   py[a[j]][Lim]=j+1;

		   	    add(a[i],Lim+1); py[a[i]][Lim+1]=i-1;

		   	    add(Lim,Lim+1);

		        Lim++;

		   }

		   else

	       {

	       	   Lim++;

	       	   add(a[j],Lim); py[a[j]][Lim]=j+1;

	       	   add(a[i],Lim); py[a[i]][Lim]=i-1;

		   }

		   EB:;

		   j=i;

		}

	}

	for(int T=1;T<=3;T++)

	{

		for(int i=1;i<=Lim;i++)

		{

			if(!match[i]) Tim++,dfs(i);

		}

	}

	for(int i=1;i<=600;i++)

	{

		if(!match[i]||No[i]||!py[i][match[i]]) continue;

		a[py[i][match[i]]]=i;

		No[i]=true;

	}

	int num=1;

	for(int i=1;i<=n;i++)

	{

		if(a[i]) continue;

		while(No[num]) num++;

		if(!a[i]&&!a[i+1])

		{

			a[i]=a[i+1]=num;

			i++;

		}

		else

		{

			a[i]=num;

		}

		num++;

	}

	for(int i=1;i<=n;i++)

	{

		cout<<a[i]<<" ";

	}

}

巴特西

CF1615G Maximum Adjacent Pairs

最新文章

热门文章