【2024NOIP模拟赛68】道路 做题记录

有 $n$ 个点，每个点有权值 $a_i$ 和 $b_i$。

点 $i$ 到点 $j$ 的有向边边权为 $\max(0,a_i-b_j)$，找到一条从 $1$ 出发，经过每个点恰好一次，最后回到 $1$ 的路径，使其最大边权最小。

$1\le n\le 10^6$，$0\le a_i,b_i\le 10^9$。

问题相当于每个点有一个入边 $b_i$ 和出边 $a_i$，求最大边权最小的哈密顿回路。

考虑下界，忽略需要成环的条件，则肯定将 $a$ 和 $b$ 分别排序后按位置一一匹配，这样是最优的。

这样会形成若干个环，考虑调整匹配使得这些环合并成一个大环。调整匹配的操作一定形如选取一对 $i,j$，交换 $b_i,b_j$，将匹配从 $(a_i,b_i),(a_j,b_j)$ 变为 $(a_i,b_j),(a_j,b_i)$，而这会合并相邻的两个环。注意到由于要求最大值最小，所以一定有 $j=i+1$，否则可以将 $[i,j]$ 内的环依次合并，一定不劣。

那么类似最小生成树，将 $n$ 对 $(i,i+1)$ 产生的贡献放到一起排序，每次选贡献最小的交换即可。

代码如下（题面不太一样）：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

template<typename T>
inline void read(T &x)
{
	char c=getchar();
	x=0;
	T w=1;
	while(c<'0'||c>'9') w=(c=='-'?-w:w),c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	x*=w;
}

typedef long long ll;

const int S=1000005,M=32767;

int n,a[S],b[S];
pair<int,int> ta[S],tb[S];
int fa[S];
pair<ll,pair<int,int> > ed[S];

inline void getin(int a[])
{
	int x,y,z;
	read(a[1]),read(a[2]),read(x),read(y),read(z);
	for(int i=3;i<=n;i++) a[i]=(a[i-1]*x%M+a[i-2]*y%M+z)%M;
}

int fnd(int x){return fa[x]==x?x:fa[x]=fnd(fa[x]);}

int main()
{
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	read(n);
	getin(a),getin(b);
	for(int i=1;i<=n;i++)
	{
		ta[i]=make_pair(a[i],i);
		tb[i]=make_pair(b[i],i);
	}
	sort(ta+1,ta+n+1);
	sort(tb+1,tb+n+1);
	for(int i=1;i<=n;i++) fa[i]=i;
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		int x=ta[i].second,y=tb[i].second;
		fa[fnd(x)]=fnd(y);
		ans=max(ans,1ll*a[x]*a[x]-1ll*b[y]*b[y]);
	}
	for(int i=1;i<=n-1;i++)
	{
		int xi=ta[i].second,yi=tb[i].second;
		int xj=ta[i+1].second,yj=tb[i+1].second;
		ed[i]=make_pair(max(
			1ll*a[xi]*a[xi]-1ll*b[yj]*b[yj],
			1ll*a[xj]*a[xj]-1ll*b[yi]*b[yi]),
			make_pair(xi,yj));
	}
	sort(ed+1,ed+n);
	for(int i=1;i<=n-1;i++)
	{
		ll w=ed[i].first;
		int x=ed[i].second.first,y=ed[i].second.second;
		if(fnd(x)==fnd(y)) continue;
		ans=max(ans,w);
		fa[fnd(x)]=fnd(y);
	}
	printf("%lld\n",ans);
	return 0;
}