啊啊啊宝宝你是一个可爱的有思维含量的分讨题

做完了 Simple Task，过了一段时间又想写分讨题，就找到了这里。

这个题也太难了（折磨了我好久好久呜呜），所以来写一篇详细的题解。

当然，如果你不是很无聊没题做，且你也不想锻炼你的代码能力，建议远离这道题目。

分析性质

先使用 ATcoder 传统艺能：找性质。

性质

B

中间一定有且仅有连续的一段是未经操作的。

证明：首先先证明，如果有，一定仅有连续的一段是未经操作的。这个很显然。因为我们只能往最左边或者右边放数，如果出现放的两段之间有一段没动过，且放的两段有至少一段不是最左或最右的，那么不是最左或最右的那一段根本就放不了数。

然后证明有一段是未经操作的。首先，一个数如果操作两次，那么操作总是可以用更少的次数等价替代掉，所以一个数最多只会操作一次。

那么只需要证明操作次数

<3N

，显然如果操作

3N

次，最中间那个数完全没必要动。所以操作次数一定

<3N

，所以总存在一段。证毕。

那么，既然

N

那么小，我们完全可以直接枚举保留的区间，然后就转化成了一个 check 的问题。我们需要在

O(N^2)

时间内 check 出保留某段区间时是否有解。

容易发现一个优美的事实：

B

中每一个数是否进行了操作，进行了什么操作是唯一确定的。且无论以什么顺序操作，答案也是根据保留的区间唯一确定的。

假设我们枚举的保留区间是

[l,r]

，那就把整个

B

划成了三部分：

[1,l)

、

[l,r]

、

(r,3N]

。

这三部分的操作自然是：向左移、不动、向右移。那么，我们只要能够确定出操作的顺序，一切就都解决了。

图论建模

关键就在于判断有没有合法的操作顺序了。由于每个数只会被操作一次，左边和右边的相对顺序就是从中间往两边的。可以抽象成一个图，

u

向

v

有一条有向边当且仅当

u

在

v

前面操作，那么这个图的拓扑排序就是一组合法解。只要让这个图无环就可以了。

等等……相对顺序？这四个字提示性极强，直接指向另外四个字——图论建模！

接下来我们就来分析还有哪些相对顺序。最好想的就是同色三个数的相对顺序，我们从这里入手。

分类讨论

不妨用 Left、Middle、Right 来代表左移、放中间不动、右移三种操作。来分类讨论每种情况：

（下面的图中，指向 L 和 R 的边对应的是从左往右对应数的操作，

123

则是操作顺序，M 不操作就不连边，不考虑操作顺序）

一、LLL

如图，可以发现

3

无论如何都不能被移动到左边，所以这种情况一旦出现就无解。

二、RRR

对称，所以同理，

3

不能被移动到右边，所以也是一旦出现就无解。

三、LLM

这样显然是合法的。不存在其他方案。

四、MRR

这样显然是合法的。不存在其他方案。

五、LMM

如图，方案唯一。

六、MMR

如图，方案唯一。

七、MMM

最简单的情况，根本不用动。

八、LLR

会发现有两种情况。

第一种：

第二种：

但是无论哪一种，都有 R 在最后一个 L 前面，不妨只加这一个约束。

九、LRR

同理，也是两种情况。

第一种：

第二种：

依然同理，无论哪一种，都有 L 在最后一个 R 前面，不妨只加这一个约束。

十、LMR

这是本题的核心，也是最大的难点。

第一种：

第二种：

这种情况就没什么性质了，所以我们需要通过 2-SAT 来判断是否存在一种合法的顺序。

2-SAT 图构造

我们需要用一种常见的方式——边转点。

我们知道，前面我们确定操作顺序的方式是位置之间连边。现在我们要确定第十种情况是先右后左还是先左后右。

我们不妨建一个新图用

[1,N]

号点表示第

i

（

1 \leq i \leq N

）种颜色是否是先右后左（不妨把原图左边的点往上放，称为向上连边），用

[N + 1, 2N]

号点表示第

i - N

（

N + 1 \leq i \leq 2N

）种颜色是否是向下连。

详细讲一下新图的结构：

[2, l - 1]

在上面，每一个点向左连边；

[r + 1, 3N - 1]

在下面，每一个点向右连边；上下有一些特殊边。

接下来，只要把边连出来就可以了！

合法判断（难点）

首先前面我们讲过了，出现 LLL 或者 RRR 一定无解。

然后来分析还有什么情况是无解的。

LLR 和 LRR

由于新图只涉及 LMR，在旧图上考虑。

可以发现，LLR 一定是向上连，LRR 一定是向下连。那么如果 LLR 在 LRR 右边，就会有下、右、上、左形成环。这种情况一定是无解的。

类似这样（不用管编号）：

LMR 和 LLR/LRR

显然，如果 LMR 在 LLR 左边或者 LRR 右边，就一定要和 LLR 或 LRR 同向，否则就会形成环。图和上面其实是一样的，只不过 LMR 取代了其中一条边，我们要为 LMR 定向。那么这个时候在新图上让不可能的方向向可能的方向连一条边，也就是说当取到了不可能的方向就一定无解。

LMR 和 LMR

那显然，两条边要同向，左边的边向下了，右边的边就不能向上；右边的边向上了，左边的边就不能向下。在新图上连边即可。

上面这几部分复杂度为

O(N^2)

。

MMM、LMM、MMR、LLM、MMR

这五种情况要判断是否有一个 M 是合法的。我们对于

l \leq i \leq r

的

B_i

进行讨论，维护一个指针从左往右扫

A

。需要基础的贪心。

显然指针不会往左，因为不移动的情况下相对顺序是不改变的，所以这部分复杂度为

O(N)

。

MMM

找到和当前

B_i

同色的配对就可以了。尽可能左边一定不劣。

LMM

用

1,2,3

表示三个相同的数从左到右的顺序。那么

B

中的

1,2,3

对应

A

中的

2,1,3

。

所以只有

A

中最左/右两个位置的可以配掉。

MMR

是对称的。

B

中的

1,2,3

对应

A

中的

1,3,2

。

所以依旧只有

A

中最左/右两个位置的可以配掉。

LLM

可以发现这种情况相对顺序不改变，非常好判。

MRR

对称，相对顺序也是不改变的。

至此，这几种情况也解决掉了，下面还有 LMR 的两个判断，是本题最难也是最烦的部分。

LMR 的 M 与其他 M 之间的限制

其他的 M 都已经被处理掉了，假设左边的 M 在

A

中位置是

p_l

，右边的 M 是

p_r

，那么当前 M 的位置

p_i

一定有

p_l<p_i<p_r

。

首先有如果

R < p_l

或者

L > p_r

，显然是无解的。

来分类讨论其他几种情况：

$R>p_r$

分四种情况讨论。

若

p_r

在右半部分：

向下连边显然错位了：

向上连呢？

是可以的！

那如果

p_r

在左半部分呢？

分析向上连：

依旧是可以的。

向下连：

错位了。

$L<p_l$

是对称的，用基本相同的方法分四种情况讨论就可以了，懒得画图了呜呜。

其余情况

会发现对建边没有限制。

LMR 的 M 与 LMR 的 M 之间的限制

显然两个 M 位置顺序不能变，没有其他要求。

假设有

l \leq i<j \leq r

，

B_i \neq B_j

。设

L_i,R_i,L_j,R_j

为

B_i

和

B_j

在

A

中对应的左右两个位置。

那么（有了前面的位置对应关系，这一部分相信可以自行画图，我画图比较麻烦，因为有

12

种情况，草稿纸上的图没法拍照，所以只给结论）：

$R_j<L_i$

必定是越位的。无解。

$L_j<L_i$

i

和

j

至多有一个向上连。

$R_j<R_i$

i

和

j

至多有一个向下连。

$L_j<R_i$

i

向下连

j

必须向下连，

j

向上连

i

必须向下连。

恭喜你建完了所有的边，现在，跑一个 2-SAT 就做完了。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
int n, N, a[105], b[105], status[105], L[105], R[105], aL[105], aR[105];
int tim, scnt, dfn[205], low[205], col[205], ins[205], pos[205], ans;
vector<int> LLL, RRR, LLR, LRR, LLM, MRR, LMM, MMR, MMM, LMR;//十种情况 
vector<int> G[205], vec[205];
stack<int> S;
void genans(int now){
	if (ans == -1)
		ans = now;
	else
		ans = min(ans, now);
}
void add(int u, int v){
	G[u].emplace_back(v);
}
void clr(){//清空 
	LLL.clear();
	RRR.clear();
	LLR.clear();
	LRR.clear();
	LLM.clear();
	MRR.clear();
	LMM.clear();
	MMR.clear();
	MMM.clear();
	LMR.clear();
	tim = 0;
	memset(L, 0, sizeof L);
	memset(R, 0, sizeof R);
	memset(aL, 0, sizeof L);
	memset(aR, 0, sizeof R);
	memset(status, 0, sizeof status);
	memset(pos, 0, sizeof pos);
	memset(dfn, 0, sizeof dfn);
	memset(low, 0, sizeof low);
	memset(col, 0, sizeof col);
	memset(ins, 0, sizeof ins);
	while (!S.empty())
		S.pop();
	for (int i = 1; i <= 200; i++){
		G[i].clear();
		vec[i].clear();
	}
}
void Tarjan(int u){
	dfn[u] = low[u] = ++tim;
	S.push(u);
	ins[u] = 1;
	for (auto v : G[u]){
		if (!dfn[v]){//树边 
			Tarjan(v);
			low[u] = min(low[u], low[v]);
		}else if (ins[v])
			low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u]){
		scnt++;
		while (1){
			int v = S.top();
			S.pop();
			col[v] = u;
			ins[v] = 0;
			if (u == v)
				break;
		}
	}
}
void genstatus(int l, int r){
	for (int i = 1; i <= N; i++){
		if (i < l)
			status[i] = 1;
		else if (l <= i && i <= r)
			status[i] = 2;
		else if (i > r)
			status[i] = 3;
	}
	for (int i = 1; i <= N; i++){//处理出每种颜色的位置 
		vec[b[i]].emplace_back(i); 
		if (status[i] == 1){
			if (!L[b[i]])
				L[b[i]] = i;
		}else if (status[i] == 3)
			R[b[i]] = i;
		if (!aL[a[i]])
			aL[a[i]] = i;
		aR[a[i]] = i;
	}
}
int GetType(int i){//获取一个颜色的类型 
	int cntL = 0, cntM = 0, cntR = 0;
	for (int pos : vec[i]){
		cntL += (status[pos] == 1);
		cntM += (status[pos] == 2);
		cntR += (status[pos] == 3);
	}
	if (cntL == 3)//按照十种情况分类 
		return 1;//LLL
	else if (cntR == 3)
		return 2;//RRR
	else if (cntL == 2 && cntR == 1)
		return 3;//LLR
	else if (cntL == 1 && cntR == 2)
		return 4;//LRR
	else if (cntL == 2 && cntM == 1)
		return 5;//LLM
	else if (cntM == 1 && cntR == 2)
		return 6;//MRR
	else if (cntL == 1 && cntM == 2)
		return 7;//LMM
	else if (cntM == 2 && cntR == 1)
		return 8;//MMR
	else if (cntM == 3)
		return 9;//MMM
	else if (cntL == 1 && cntR == 1 && cntM == 1)
		return 10;//LMR
}
void RubbishSorting(int l, int r){
	for (int i = 1; i <= n; i++){
		int cntL = 0, cntM = 0, cntR = 0;
		for (int pos : vec[i]){
			cntL += (status[pos] == 1);
			cntM += (status[pos] == 2);
			cntR += (status[pos] == 3);
		}
		if (cntL == 3)//按照十种情况分类 
			LLL.emplace_back(i);
		else if (cntR == 3)
			RRR.emplace_back(i);
		else if (cntL == 2 && cntR == 1)
			LLR.emplace_back(i);
		else if (cntL == 1 && cntR == 2)
			LRR.emplace_back(i);
		else if (cntL == 2 && cntM == 1)
			LLM.emplace_back(i);
		else if (cntM == 1 && cntR == 2)
			MRR.emplace_back(i);
		else if (cntL == 1 && cntM == 2)
			LMM.emplace_back(i);
		else if (cntM == 2 && cntR == 1)
			MMR.emplace_back(i);
		else if (cntM == 3)
			MMM.emplace_back(i);
		else if (cntL == 1 && cntR == 1 && cntM == 1)
			LMR.emplace_back(i);
	}
}
int check(int l, int r){
	//钦定 L 上 R 下，向上连为 [1, n]，向下连为 [n + 1, 2n] 
	genstatus(l, r);
	RubbishSorting(l, r);
	
	//判断 LLL 和 RRR 的无解情况 
	if (LLL.size() || RRR.size())
		return -1;
	//LLL 最右侧的一个无法移到左边；RRR 对称，所以存在即无解
	
	//判断 LRR 和 LLR 的无解情况
	for (auto c1 : LRR)
		for (auto c2 : LLR){
			if (L[c1] < L[c2] && R[c1] < R[c2])
				return -1;
		} 
	//样例很良心给了这个，这样会成环 
	
	//判断 LMR 和 LLR/LRR 的情况
	for (auto c1 : LMR){
		for (auto c2 : LLR){
			if (L[c1] < L[c2] && R[c1] < R[c2]){
				//必须向上连 
				add(c1 + n, c1);
			}
		}
		for (auto c2 : LRR){
			if (L[c2] < L[c1] && R[c2] < R[c1]){
				//必须向下连 
				add(c1, c1 + n);
			}
		}
	}
	//通过 LLR 和 LRR 可以唯一确定 LMR 的方向 
	
	//判断 LMR 和 LMR 的情况
	for (auto c1 : LMR){
		for (auto c2 : LMR){
			if (L[c1] < L[c2] && R[c1] < R[c2])
				add(c1 + n, c2 + n);
			//左边向下，右边不能向上，否则成环
			if (L[c2] < L[c1] && R[c2] < R[c1])
				add(c1, c2);
			//右边向上，左边不能向下，否则成环 
		}
	}
	//两个 LMR 需要同向
	
	//判断 MMM、LLM、MRR、LMM、MMR 是否合法 
	int p = 1;
	for (int i = l; i <= r; i++){//中间保留部分 
		int typ = GetType(b[i]);
		if (typ == 9){//MMM
			while (p <= N && a[p] != b[i])
				p++;
			if (p > N)
				return -1;
			pos[i] = p;
			p++;
		}else if (typ == 7){//LMM
			while (p <= N && p != aL[b[i]] && p != aR[b[i]])
				p++;
			if (p > N)
				return -1;
			pos[i] = p;
			p++;
		}else if (typ == 8){//MMR
			while (p <= N && p != aL[b[i]] && p != aR[b[i]])
				p++;
			if (p > N)
				return -1;
			pos[i] = p;
			p++;
		}else if (typ == 5){//LLM
			while (p <= N && p != aR[b[i]])
				p++;
			if (p > N)
				return -1;
			pos[i] = p;
			p++;
		}else if (typ == 6){//MRR
			while (p <= N && p != aL[b[i]])
				p++;
			if (p > N)
				return -1;
			pos[i] = p;
			p++;
		}
	}
	//处理出每个 M 在 a 中对应的位置
	
	// 判断 LMR 的 M 限制 
	for (int i = l; i <= r; i++){
		int x = GetType(b[i]);
		if (x != 10)
			continue;
		//找到左边和右边被限制的位置，显然当前位置一定得在两个位置中间
		int ml = 0, mr = N + 1;
		for (int j = i - 1; j >= l; j--){
			if (pos[j]){
				ml = pos[j];
				break;
			}
		}
		for (int j = i + 1; j <= r; j++)
			if (pos[j]){
				mr = pos[j];
				break;
			}
		//当前位置应该在 (ml, mr) 区间内
		if (aL[b[i]] > mr || aR[b[i]] < ml)
			return -1;
		if (aL[b[i]] < ml){
			//向下连 
			add(b[i], b[i] + n);
		}
		if (aR[b[i]] > mr){
			//向上连 
			add(b[i] + n, b[i]);
		}
	}
	//基于 M 的位置限制
	
	// 显然有 LMR 和 LMR 之间的 M 不能相互越位，进行判断
	for (int i = l; i <= r; i++){
		int x = GetType(b[i]);
		if (x != 10)
			continue;
		for (int j = i + 1; j <= r; j++){
			int y = GetType(b[i]);
			if (y != 10)
				continue;
			if (aR[b[j]] < aL[b[i]])
				return -1;
			if (aL[b[j]] < aL[b[i]]){
				add(b[i], b[j] + n);
				add(b[j], b[i] + n);
			}
			if (aR[b[j]] < aR[b[i]]){
				add(b[i] + n, b[j]);
				add(b[j] + n, b[i]);
			}
			if (aL[b[j]] < aR[b[i]]){
				add(b[i] + n, b[j] + n);
				add(b[j], b[i]);
			}
		}
	}
	//一定要搞清楚了
	
	//Tarjan 主体
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			Tarjan(i);
			
	// 判断是否有解 
	for (int i = 1; i <= n; i++)
		if (col[i] == col[i + n])
			return -1;//矛盾了 
			
	return N - (r - l + 1);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	N = 3 * n;
	ans = -1;
	bool qwq = 0;
	for (int i = 1; i <= N; i++)
		cin >> a[i];
	for (int i = 1; i <= N; i++){
		cin >> b[i];
		if (a[i] != b[i])
			qwq = 1;
	}
	if (!qwq){
		cout << 0;
		exit(0);
	}
	for (int len = N - 1; len; len--){
		for (int l = 1; l + len - 1 <= N; l++){
			clr();
			int r = l + len - 1;
			genans(check(l, r));
			if (ans != -1){
				cout << ans;
				exit(0);
			}
		}
	}
	cout << ans;
	return 0;
}

后记

是微渺/的希望/我们依然前行没有光指引/往前吧失去吧不要停留。

这题确实很可怕，但是，把时间用在所热爱的一切上，用尽全力，总会看到成果的。

啊啊啊宝宝你是一个可爱的有思维含量的分讨题

文章操作

分析性质

性质

图论建模

分类讨论

一、LLL

二、RRR

三、LLM

四、MRR

五、LMM

六、MMR

七、MMM

八、LLR

九、LRR

十、LMR

2-SAT 图构造

合法判断（难点）

LLR 和 LRR

LMR 和 LLR/LRR

LMR 和 LMR

MMM、LMM、MMR、LLM、MMR

MMM

LMM

MMR

LLM

MRR

LMR 的 M 与其他 M 之间的限制

$R>p_r$

$L<p_l$

其余情况

LMR 的 M 与 LMR 的 M 之间的限制

$R_j<L_i$

$L_j<L_i$

$R_j<R_i$

$L_j<R_i$

后记

相关推荐

评论

啊啊啊宝宝你是一个可爱的有思维含量的分讨题

文章操作

分析性质

性质

图论建模

分类讨论

一、LLL

二、RRR

三、LLM

四、MRR

五、LMM

六、MMR

七、MMM

八、LLR

九、LRR

十、LMR

2-SAT 图构造

合法判断（难点）

LLR 和 LRR

LMR 和 LLR/LRR

LMR 和 LMR

MMM、LMM、MMR、LLM、MMR

MMM

LMM

MMR

LLM

MRR

LMR 的 M 与其他 M 之间的限制

R>prR>p_rR>pr​

L<plL<p_lL<pl​

其余情况

LMR 的 M 与 LMR 的 M 之间的限制

Rj<LiR_j<L_iRj​<Li​

Lj<LiL_j<L_iLj​<Li​

Rj<RiR_j<R_iRj​<Ri​

Lj<RiL_j<R_iLj​<Ri​

后记

相关推荐

评论

$R>p_r$

$L<p_l$

$R_j<L_i$

$L_j<L_i$

$R_j<R_i$

$L_j<R_i$