CF2117E 题解
songtaoran
·
·
题解
前言
目前的题解都是只说结论，我来证明一下。
首先，观察题面：
可以进行一次删除操作。
选取 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。
此时我们可以交替赋值：
情况 $2$：有一个下标 $i$ 使得 $a_i = a_{i + 1}(b_i = b_{i + 1})$。
赋值一次就变成情况 $1$ 了。
情况 $3$：$a_i(b_i)$ 在 $i + 1$ 的后面（不包括 $i + 1$）出现过。
分讨。假设出现过的这个数的下标为 $j$。
1. $a_i = a_j(b_i = b_j)$，$j - i + 1$ 为偶数。手推一下，发现此时不断赋值最终会变成情况 $1$。
2. $a_i = a_j(b_i = b_j)$，$j - i + 1$ 为奇数。怎么办呢？别忘了，还有一个条件没用：**可以进行一次删除操作。** 于是我们进行一次删除操作，$j - i + 1$ 就变成偶数了。
3. $a_i = b_j(b_i = a_j)$，$j - i + 1$ 为奇数。仍然是不断赋值。
4. $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$](https://codeforces.com/problemset/submission/2117/326213467)
码字不易，求赞 qwq。