题解：AT_abc399_d [ABC399D] Switch Seats

解法

显然的，本题中每个数出现且仅出现两次，于是在排除了同一个数字相邻情况之后，只需统计满足两次出现且都相邻的数对

(i,j)

的个数。
所以此题我们只需要从后往前扫，判断出现次数大于等于二的

(i,j)

即可。
但特别的，会有 1221 和 121……2 两种特殊情况，需要注意。

代码

CPP

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

题解：AT_abc399_d [ABC399D] Switch Seats

文章操作

解法

代码

相关推荐

评论

题解：AT_abc399_d [ABC399D] Switch Seats