[NOI2009]变换序列(二分图匹配)
时间: 2023-08-06 16:13:22 浏览: 42
题目描述
给出一个由 $n$ 个数排成的序列,你可以进行如下操作:
交换相邻的两个数。
将该序列中的第 $k$ 个数改为 $x$。
你的任务是将该序列变成一个等差数列。
输入格式
第一行包含两个整数 $n$ 和 $m$,表示序列长度和操作次数。
第二行包含 $n$ 个整数,表示初始序列。
接下来 $m$ 行,每行描述一个操作,格式如下:
1. swap x y:表示交换原序列中下标为 $x$ 和 $y$ 的数。
2. set x y:表示将原序列中下标为 $x$ 的数修改为 $y$。
输出格式
如果无法将序列变成等差数列,输出 Impossible。
否则,第一行输出 Yes。
第二行输出变换后的序列。
数据范围
$1 \leq n \leq 5000$
$1 \leq m \leq 10^5$
$1 \leq |a_i|, |x|, |y| \leq 10^9$
输入样例1:
5 3
5 4 3 2 1
set 2 6
swap 1 2
set 4 1
输出样例1:
Yes
6 4 3 1 2
输入样例2:
5 3
5 4 3 2 1
set 2 6
swap 1 2
set 4 10
输出样例2:
Impossible
算法1
(二分图匹配) $O(n^3)$
由于每次可以交换相邻的两个数,可以通过这个操作来使序列中的某个数字移动到另一个位置,因此可以考虑每个数字在序列中的位置之间建立一条边,如果两个数字之间可以通过交换相邻数变成等差数列,则在它们之间连一条边。
具体而言,如果有两个数字 $a,b$,假设它们当前的位置分别为 $i,j$,那么它们之间就可以连一条边,如果它们能够使得序列变成等差数列。
对于 $set$ 操作,可以考虑将该位置对应的点与其他点之间的边全部删除,然后重新建立连接。
最后,判断是否存在一个匹配,使得所有点都与另一个点进行匹配,如果存在,则说明可以通过交换相邻数的方式使得序列变成等差数列。
时间复杂度
- 建图 $O(n^2)$
- 匈牙利算法 $O(n^3)$
C++ 代码