ABC399.D题解

题目

D - Switch Seats

算法标签: 模拟, 哈希

思路

对于序列中两个相同数字不能在同一个位置, 并且可以通过交换使得四个数字两两在相同位置

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>

using namespace std;

typedef pair<int, int> PII;
const int N = 4e5 + 10;

int n, w[N];

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int T;
	cin >> T;
	while (T--) {
   
		cin >> n;
		vector<int> w(2 * n + 1);
		vector<int> pos[n + 1];

		for (int i = 1; i <= n * 2; ++i) {
   
			cin >> w[i];
			pos[w[i]].push_back(i);
		}

		set<PII> ans;
		for (int i = 1; i + 1<= n * 2; ++i) {
   
			int a = w[i], b = w[i + 1];
			if (a == b) continue;
			if (pos[a][0] + 1 == pos[a][1]) continue;
			if (pos[b][0] + 1 == pos[b][1]) continue;

			vector<int> vec{
   pos[a][0], pos[a][1], pos[b][0], pos[b][1]};
			sort(vec.begin(), vec.end());
			if (vec[0] + 1 == vec[1] && vec[2] + 1 == vec[3]) {
   
				ans.insert(minmax(a, b));
			}
		}
		cout << ans.size() << "\n";
	}

	return 0;
}