CF2117E 题解

前言

目前的题解都是只说结论，我来证明一下。
首先，观察题面：
可以进行一次删除操作。
选取 $i$ ，然后使得 $a_i = b_{i + 1}$ 或 $b_i = a_{i + 1}$ 。

结论

当

a_n = b_n

时，答案为

n

。
否则，答案为最大的下标

i

满足

a_i = b_i

或

a_i = a_{i + 1}

或

b_i = b_{i + 1}

或

a_i(b_i)

在

i + 1

（不包括

i + 1

）后出现过。

证明

情况

1

：有一个下标

i

使得

a_i = b_i

。
此时我们可以交替赋值：

a_{i - 1} = b_i,b_{i - 1} = a_i,a_{i - 2} = b_{i - 1},b_{i - 2} = a_{i - 1}\dots

，这样答案就是

i

了。

情况

2

：有一个下标

i

使得

a_i = a_{i + 1}(b_i = b_{i + 1})

。
赋值一次就变成情况

1

了。

情况

3

：

a_i(b_i)

在

i + 1

的后面（不包括

i + 1

）出现过。
分讨。假设出现过的这个数的下标为

j

。

$a_i = a_j(b_i = b_j)$ ， $j - i + 1$ 为偶数。手推一下，发现此时不断赋值最终会变成情况 $1$ 。
$a_i = a_j(b_i = b_j)$ ， $j - i + 1$ 为奇数。怎么办呢？别忘了，还有一个条件没用：可以进行一次删除操作。 于是我们进行一次删除操作， $j - i + 1$ 就变成偶数了。
$a_i = b_j(b_i = a_j)$ ， $j - i + 1$ 为奇数。仍然是不断赋值。
$a_i = b_j(b_i = a_j)$ ， $j - i + 1$ 为偶数。可以进行一次删除操作。 仍然是删除一次， $j - i + 1$ 就变成奇数了。

这时有人就要问了：为什么是

i + 1

的后面而不是

i

的后面呢？
如果是

i

的后面（不包括

i

），那么 1. 和 2. 在

j = i + 1

情况下就是情况

2

，3. 在

j = i + 1

情况下不满足

j - i + 1

为奇数，4. 在

j = i + 1

情况下无解，所以还是相当于在

i + 1

的后面，还得做特判，过于麻烦。

代码

CPP

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
ll T, n, a[200010], b[200010];
bool vis[200010]; 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> T;
	while(T--){
		memset(vis, 0, sizeof vis);
		cin >> n;
		for(ll i = 1; i <= n; i++) cin >> a[i];
		for(ll i = 1; i <= n; i++) cin >> b[i];
		if(a[n] == b[n]){
			cout << n << endl; continue;
		}
		ll mx = 0;
		for(ll i = n - 1; i > 0; i--){
			if(a[i] == b[i] || a[i + 1] == a[i] || b[i + 1] == b[i] || vis[a[i]] || vis[b[i]]){
				mx = i; break;
			}
			vis[a[i + 1]] = vis[b[i + 1]] = 1;
		}
		cout << mx << endl;
	}
	return 0;
}

提交记录

326213467

码字不易，求赞 qwq。

文章操作

前言

结论

证明

代码

相关推荐

评论

CF2117E 题解