题解：AT_abc399_d [ABC399D] Switch Seats

_qumingnan_ · 2025-03-30 09:09:04 · 题解

题目跳楼机

正文开始

阅读理解：

有 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 相邻时也不合法。

代码实现：

#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;
}