专栏文章

题解：P9001 [CEOI 2022] Parking

MMeta_Morph
P9001题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minwwmtp
此快照首次捕获于
2025/12/02 09:41
3 个月前
此快照最后确认于
2025/12/02 09:41
3 个月前
查看原文

P9001 [CEOI 2022] Parking 题解

前言

笔者认为自己的分析较有利于代码实现，而且理解也来的容易。

知识点

构造，模拟，图论，环，链。

分析

暴力

首先对于 M≤4M\le 4 的部分有暴力 BFS，可以 O(m2(2m)!)O(m^2(2m)!) 过。

性质

然后我们考虑找性质，对于一种颜色的车，有三种类型：
  1. 两辆车都是「底下的车」。
  2. 一辆车是「底下的车」，另一辆是「顶上的车」。
  3. 两辆车都是「底上的车」。
那么区分开这些类型之后，发现 2N≤M2N\le M 的部分只要略加讨论就可以过：
  1. 两辆车都是「底下的车」：选择一个作为最后停留的位置。
  2. 一辆车是「底下的车」，另一辆是「顶上的车」：选择「底下的车」所在处作为最后停留的位置。
  3. 两辆车都是「底上的车」：找一个空位把两辆车都塞进去。
那么由于满足 2N≤M2N\le M，会有很多原本就空着的位置，那么即使很随意地选择也可以使上面的方案合法，我们用拓扑排序就可以过。

建图

接下来我们继续分析。考虑移动原图，我们将数字一样的放到相邻，那么样例就变成了：
0320411324\begin{matrix} 0 & 3 & 2 & 0 & 4\\ 1 & 1 & 3 & 2 & 4\\ \end{matrix}
这样变得非常容易观察，我们可以将其分为两个部分，其中 44\begin{matrix} 4\\ 4\\ \end{matrix} 的部分较为简单，就不赘述（但是记得特判）。剩下的就是：
03201132\begin{matrix} 0 & 3 & 2 & 0 \\ 1 & 1 & 3 & 2 \\ \end{matrix}
这似乎像一条链，将两个点堆在一起，于是我们想到了图论建模：将每个车位中的两辆车的颜色连一条边（如果有两辆）。
由于每个点度数 ≤2\le 2，那么最后会形成一堆链和简单环，上面就是我们最简单的一种环。

处理

于是我们对各种链和环的情况讨论，会发现其实此时求解最小步数已经非常简单，剩下的就是如何让方案合法。其主要影响因素其实是类型 2（两辆车都是「底上的车」），因为有类型 2 就代表必须有空位给它用，所以我们可以以类型 2 作为依据来分类讨论：
  1. 链，没有类型 2：
    就是我们上面举的例子，这样的链一定有一个类型 0 和一堆类型 1，比如下面这个：
    0a1a2a3…akak+1…an−1an0a1a2a3…akxxak+1…an−1an\begin{matrix} 0 & a_1 & a_2 & a_3 & \ldots & a_{k} & a_{k+1} & \ldots & a_{n-1} & a_n & 0 \\ a_1 & a_2 & a_3 & \ldots & a_{k} & x & x & a_{k+1} & \ldots & a_{n-1} & a_n \\ \end{matrix}
    其中 xx 左边或右边的 aa 均可能没有。
    那么这种情况处理很简单，也不用占用额外的空位，反而在处理完之后会多出一个空位。
  2. 链，有类型 2：
    其实类型 2 可以看作起一个连接作用，将很多上面情况 1 的链连接起来就是我们这里的情况 2，例如下面中的 b1b_1：
    0a1,1…a1,n1b1b1a2,1…a2,n20a1,1…x1 x1…a1,n1a2,1…x2 x2…a2,n2\begin{matrix} 0 & a_{1,1} & \ldots & a_{1,n_1} & b_1 & b_1 & a_{2,1} & \ldots & a_{2,n_2} & 0 \\ a_{1,1}& \ldots & x_1 \ x_1 & \ldots & a_{1,n_1} & a_{2,1}& \ldots & x_2 \ x_2 & \ldots & a_{2,n_2} \\ \end{matrix}
    于是我们需要一个额外的空位来处理 b1b_1，然后就变成了两个情况 1。
    那么如果是多个，那么也只需要一个额外空位，因为将能处理的情况 1 处理完之后会多出一个空位，弥补了我们刚刚用掉的那个。
    当然这个情况在处理完之后也会多出一个空位。
  3. 环，没有类型 2：
    这种清况比较简单，毕竟没有类型 2，但是要成环的话，每个车位上下两个必须都有一个，上下总数需要相同，那么就不能有类型 0。也就是说只能有类型 1，例如：
    a1a2a3…an−1ana2a3…an−1ana1\begin{matrix} a_1 & a_2 & a_3 & \ldots & a_{n-1} & a_n \\ a_2 & a_3 & \ldots & a_{n-1} & a_n & a_1 \\ \end{matrix}
    那么我们只需要一个额外的空位就可以解决。不过这里的处理细节容易出错。
  4. 环，有且只有一个类型 2：
    那么这种情况可以看做情况 1 的链用一个类型 2 首尾相接，用一个额外的空位将类型 2 处理了之后，剩下的就是情况 1 了。
    ba1a2a3…akak+1…an−1anba1a2a3…akxxak+1…an−1an\begin{matrix} b & a_1 & a_2 & a_3 & \ldots & a_{k} & a_{k+1} & \ldots & a_{n-1} & a_n & b \\ a_1 & a_2 & a_3 & \ldots & a_{k} & x & x & a_{k+1} & \ldots & a_{n-1} & a_n \\ \end{matrix}
  5. 环，有多于一个类型 2：
    类似情况 4，去掉一个类型 2 之后就变成了情况 2，那么这个需要两个额外的空位。
    b2a1,1…a1,n1b1b1a2,1…a2,n2b2a1,1…x1 x1…a1,n1a2,1…x2 x2…a2,n2\begin{matrix} b_2 & a_{1,1} & \ldots & a_{1,n_1} & b_1 & b_1 & a_{2,1} & \ldots & a_{2,n_2} & b_2 \\ a_{1,1}& \ldots & x_1 \ x_1 & \ldots & a_{1,n_1} & a_{2,1}& \ldots & x_2 \ x_2 & \ldots & a_{2,n_2} \\ \end{matrix}
简单整理一下，可以得到：
类型需要额外空位数产生额外空位数
情况 1：链，没有类型 201
情况 2：链，有类型 211
情况 3：环，没有类型 210
情况 4：环，有且只有一个类型 210
情况 5：环，有多于一个类型 220
那么很明显，我们从情况 1 顺次处理到情况 5 就可以做到尽可能合法，剩下的代码实现也比较简单。

实现

输入和预处理

首先考虑处理出每种颜色的类型 tyty 和位置 pos0/1pos_{0/1}。

建图

我们先找出链，考虑从每个链的一端（注意一端的度数也可以是 00）开始深搜，然后按数量区分为情况 1 和情况 2。
为了方便，接着我们以类型 2 作为起点，搜出每个有类型 2 的环，按数量区分为情况 4 和情况 5。
最后剩下的就是情况 3 了，无需区分。

处理

我们将链中情况 1 用双指针处理，然后情况 2 将类型 2 处理了之后就是情况 1，那么链的部分处理完了。
对于情况 3 的链，我们直接循环扫一遍就可以解决。
而对于情况 4 和情况 5，我们把作为起点的类型 2 处理了就变成链的部分了。

检查

注意检查原本就匹配的，以及判断合法性！！！

代码

时空复杂度 O(n)O(n)。
CPP
constexpr int N(2e5+10);

int n,m,ans;
int rt[N],ty[N],cnt[N];
int pos[N][2];
vector<int> Emp,Rt[5];
vector<int> g[N],vec[N];
vector<pair<int,int>> Ans;

void Move(int x,int y) { return Ans.emplace_back(x,y); }

void dfs(int u) {
	if(ty[u]==2)++cnt[rt[u]];
	vec[rt[u]].push_back(u);
	for(int v:g[u])if(!rt[v])rt[v]=rt[u],dfs(v);
}

void List(vector<int> &vec) {
	for(int l(0),r(0); l<(int)vec.size(); l=r+2) {
		r=l;
		while(r+1<(int)vec.size()&&ty[vec[r+1]]!=2)++r;
		if(r+1<(int)vec.size()) {
			const int v(vec[r+1]),emp(Emp.back());
			Emp.pop_back(),Move(pos[v][0],emp),Move(pos[v][1],emp);
		}
		int h(l),t(r);
		while(h<t) {
			const int &v(vec[ty[vec[h]]?h++:t--]);
			Move(pos[v][1],pos[v][0]);
		}
		const int &v(vec[h]);
		Move(pos[v][1],pos[v][0]),Emp.push_back(pos[v][1]);
	}
}

template<const bool ty>void Circle(vector<int> &vec) {
	if(vec.empty())return;
	if(!ty) {
		if(pos[vec.front()][0]!=pos[vec.back()][1])reverse(vec.begin(),vec.end());
		const int v(vec.back()),emp(Emp.back());
		Emp.pop_back(),Move(pos[v][1],emp),pos[v][1]=emp;
		for(int v:vec)Move(pos[v][1],pos[v][0]);
		Emp.push_back(emp);
		return;
	}
	const int v(vec.front()),emp(Emp.back());
	Emp.pop_back(),Move(pos[v][0],emp),Move(pos[v][1],emp);
	vec.erase(vec.begin()),List(vec);
}

signed main() {
	/*DE("Input & Init");*/
	I(n,m);
	FOR(i,1,m) {
		int u,v;
		I(u,v);
		if(u&&v&&u!=v)g[u].push_back(v),g[v].push_back(u);
		!u?Emp.push_back(i),0:pos[u][pos[u][0]>0]=i;
		if(v)++ty[v],pos[v][pos[v][1]<=0]=i;
	}
	/*DE("Build");*/
	// lists
	FOR(i,1,n)if(!rt[i]&&pos[i][0]!=pos[i][1]&&(int)g[i].size()<=1)
		rt[i]=i,dfs(i),Rt[cnt[i]>0].push_back(i);
	// circles
	FOR(i,1,n)if(!rt[i]&&pos[i][0]!=pos[i][1]&&ty[i]==2)
		rt[i]=i,dfs(i),Rt[(cnt[i]<=1?3:4)].push_back(i);
	FOR(i,1,n)if(!rt[i]&&pos[i][0]!=pos[i][1])
		rt[i]=i,dfs(i),Rt[2].push_back(i);
	/*DE("Solve");*/
	for(int u:Rt[0])List(vec[u]);
	if(Emp.empty()&&(!Rt[1].empty()||!Rt[2].empty()||!Rt[3].empty()||!Rt[4].empty()))
		return puts("-1"),0; // check point 1
	for(int u:Rt[1])List(vec[u]);
	if((int)Emp.size()<=1&&!Rt[4].empty())return puts("-1"),0; // check point 2
	for(int u:Rt[2])Circle<0>(vec[u]);
	for(int u:Rt[3])Circle<1>(vec[u]);
	for(int u:Rt[4])Circle<1>(vec[u]);
	/*DE("Output");*/
	O(Ans.size(),'\n');
	for(const pair<int,int> &p:Ans)O(p.first,' ',p.second,'\n');
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...