专栏文章

题解：AT_abc399_d [ABC399D] Switch Seats

EEmplace
AT_abc399_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miprs52o
此快照首次捕获于
2025/12/03 16:53
3 个月前
此快照最后确认于
2025/12/03 16:53
3 个月前
查看原文

思路

性质

我们可以发现，只有相邻两个数满足条件，且不能相等，并且两个数都不能与旁边的数相等。它们对应的数也是这样。

做法

记录每个数出现的两次位置。然后对于每个数，只需要求它的另外一个数与它下一个数的另外一个数即可，然后按照性质判断即可。

Code

CPP
#include<bits/stdc++.h>
using namespace std;
int t,n,a[500000],cnt,t1[500000],t2[500000];
int main(){
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=2*n;i++) t1[i]=0,t2[i]=0;
		for(int i=1;i<=2*n;i++){
			cin>>a[i];
			if(!t1[a[i]]) t1[a[i]]=i;
			else t2[a[i]]=i;
		}
		cnt=0;
		for(int i=1;i<=2*n-1;i++){
			int j,k;
			if(t1[a[i]]==i) j=t2[a[i]];
			else j=t1[a[i]];
			if(t1[a[i+1]]==i+1) k=t2[a[i+1]];
			else k=t1[a[i+1]];
			if(abs(k-j)==1&&abs(j-i)>1&&abs(k-i-1)>1){
				cnt++;
			}
		}
		cout<<cnt/2<<endl;
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...