正文开始

阅读理解：

有

2n

个数，其中

1\sim n

搞好出现

2

次。现在求有多少对数本不相邻，但一个数和另外一对数中一个交换后，两队数都相邻。

思路：

令一对数为

x

，另一对为

y

。

很显然，想要交换后都相邻，那就必须

x

与

y

分别相邻，于是就可以存下每个数第一次出现的位置，然后看

l_{a_i}

与

l_{a_{i-1}}

是否相邻即可。

注：如

l_{a_i}

与

i

相邻，或

l_{a_{i-1}}

与

i

相邻时也不合法。

代码实现：

CPP

#include<bits/stdc++.h>
using namespace std;
int T;
int n;
int a[400005],t[400005],ans;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=2*n;i++){
			cin>>a[i];
			if(!t[a[i]])t[a[i]]=i;//存第一次出现的位置。 
		}
		for(int i=2;i<=2*n;i++){
			int x=t[a[i]],y=t[a[i-1]];//a[i] 第一次出现的位置与 a[i-1] 第一次出现的位置。 
			if(abs(i-x)<=1||abs(i-1-y)<=1||abs(x-y)!=1)continue;//如果相邻，或者 x 与 y 不相邻，那就不合法。 
			ans++;
		}
		cout<<ans<<'\n';
		for(int i=1;i<=2*n;i++)t[a[i]]=0;
		ans=0;
		//多测不清空，爆 0 两行泪 
	}	
	return 0;
}

题解：AT_abc399_d [ABC399D] Switch Seats

文章操作

正文开始

阅读理解：

思路：

代码实现：

相关推荐

评论

题解：AT_abc399_d [ABC399D] Switch Seats