cf2117E

原题链接：https://codeforces.com/contest/2117/problem/E

题目背景：

       给定两个数组a,b，可以执行多次以下操作：选择 i (1 <= i <= n - 1)，并设置  或，也可以在执行上述操作前执行一次删除任意  和 。求最大匹配数， 即可算得一点匹配数。

思路：

       通过题目不难发现以下几点规律：

1. 如果 ，其答案就为 n 。
2. 如果  ，就可以将 i 之前所有的元素都变成相同的元素，既答案为 i 。
3. 如果  或 ，也可以将 i 之前所有的元素都变成相同的元素。
4. 如果当前  或 ，在 i + 1 (不包含) 之后出现过，也可以将 i 之前所有的元素都变成相同的元素。

        第四条证明：设 a = [1,2,5,4,6]，b = [3,3,2,1,3]，st[num]表示num在i+1之后是否出现过。

        逆推从 i = 4 开始（下标从0开始）；

        首先 i = 4， 6 != 3。

        i = 3，4 != 1 && 4 != 3 && 1 != 6；将 st[6] = st[3] = 1。

        i = 2，5 != 2 && 5 != 4 && 2 != 1 && st[5] == 0 && st[2] ==0；将 st[4] = st[1] = 1

        i = 1，st[2] = 1，答案为2。

        图解（数字右下角的红色数字代表可以通过操作将数字变为红色数字）：

        

        如果样例是 a = [1,2,5,4,3]，b = [3,3,2,1,6] 呢？

        我们还有一个操作2可以在执行全部所以操作之间使用，只需删除中间的任意一对元素即可。

        图解：

数据范围：

        n 总和不超过 2e5。

时间复杂度：

        O(n)。

ac代码： 

#include <bits/stdc++.h>#define ioscc ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define me(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()
#define sz(a) ((int)(a).size())
#define pb(a) push_back(a)
using namespace std;typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<bool> vb;const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAX = (1ll << 31) - 1;
const int MIN = 1 << 31;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cout << a[i] << ' ';return os;
}template <class T>
istream &operator>>(istream &in, vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cin >> a[i];return in;
}/* ----------------- 有乘就强转，前缀和开ll ----------------- */void solve()
{int n;cin >> n;vi a(n + 10), b(n + 10);cin >> a >> b;if (a[n - 1] == b[n - 1]){cout << n << endl;return;}vi st(n + 10, 0);ll ans = 0;for (int i = n - 2; ~i; --i){if (a[i] == a[i + 1] || b[i + 1] == b[i] || a[i] == b[i] || st[a[i]] || st[b[i]]){ans = i + 1; // 下标从0开始break;}st[a[i + 1]] = st[b[i + 1]] = 1;}cout << ans << endl;
}int main()
{ioscc;int T;cin >> T;while (T--)solve();return 0;
}