题解：AT_abc399_d [ABC399D] Switch Seats

· · 题解

解法

显然的，本题中每个数出现且仅出现两次，于是在排除了同一个数字相邻情况之后，只需统计满足两次出现且都相邻的数对 (i,j) 的个数。
所以此题我们只需要从后往前扫，判断出现次数大于等于二的 (i,j) 即可。
但特别的，会有 1221 和 121……2 两种特殊情况，需要注意。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=4e5+10;
int a[N];
map<pair<int,int>,int>mp;
signed main()
{
    int T,n;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        int ans=0;
        n=n*2;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int lx,ly;
        lx=ly=0;
        for(int i=2;i<=n;i++)
        {
            if(a[i]==a[i-1])
                continue;
            int x=a[i];
            int y=a[i-1];
            if(x<y)
             swap(x,y);
            if(x==lx&&y==ly)
            {
                lx=ly=0;
                continue;
            }
            lx=x;
            ly=y;
            mp[make_pair(x,y)]++;
            if(mp[make_pair(x,y)]==2)
                ans++;
        }
        cout<<ans<<endl;
        for(int i=2;i<=n;i++)
        {
            int x=a[i];
            int y=a[i-1];
            if(x<y)
            swap(x,y);
            mp[make_pair(x,y)]=0;
        }
    }
    return 0;
}