洛谷7月月赛题解 C P6687

算法1:

直接puts(“dldsgay!!1”);，期望获得 1 分。

算法2:

直接puts(“dldsgay!!1”);，期望获得 1 分。



算法3:

不难发现，由于只有一列，无法进行翻转操作。所以只需要判断当前状态和目标状态是否一致，若一致

则puts("0");，不一致则puts("dldsgay!!1");。期望获得6分。



算法4:

有两列时，可以进行翻转操作了。不难发现，可达的状态只有两种，于是只需要判断这两种状态中有没

有目标状态即可。结合算法3，期望得分11分。

判断无解:

先考虑清楚无解的情况:

如果存在现有状态的一列中的两个数，在目标状态中不在一列，则肯定无解。

再考虑判断上下位置是否合法:显然对一列进行一次翻转之后，上下关系会交换一次。若从第z列翻转

到第y列，则上下关系会交换|z一非次。那么对于现有状态的一列，判断其翻转到目标状态时，上下关

系是否与其一致。若不一致则一定不可能合法。

判断这两条之后，就能判定是否有解了。

深入思考，问题转化:

考虑到翻转操作不可能将一列拆散，事实上我们可以把一列“绑在一起”，直接看成一个序列的问题。

现在问题就是:每次交换两个数，求问将现有序列交换成目标序列的最少步数。



算法5

直接BFs，实现优秀的话，结合算法4，期望得分25分。

算法6

设现有序列第i个位置上的数为A;，目标序列第i个位置上的数为B。

设$C_B$= $i$，则令$A$=$C_{A_i}$。

则不难发现，对A操作使其变成B，等价于对4操作使得4升序。

考虑到我们的操作是每次交换两个数，则不难发现最小操作次数为逆序对数。

使用冒泡排序计算，复杂度$O(n^2)$，期望得分63分。

使用归并排序、树状数组或线段树等数据结构计算，复杂度O(n log n)，期望得分100分。

参考代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
using namespace std;
const int maxn = 2e6+10;

int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c < '0' || c > '9'){if(c=='-')f=-1;c=getchar();}
	while(c >= '0' && c <= '9'){x=(x<<3)+(x<<1)+c-48;c=getchar();}
	return x*f;
}

int k,m,n;
int a[maxn],b[maxn],c[maxn],d[maxn],fa[maxn],p[maxn];
pair<int,int> P[maxn];
int sum[maxn];
void add(int x){for(int i=x;i<=n;i+=i&-i)sum[i]++;}
int query(int x){int SUM=0;for(int i=x;i;i-=i&-i)SUM+=sum[i];return SUM;}
int main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)b[i]=read();
	for(int i=1;i<=n;i++){c[i]=read();P[c[i]]=make_pair(i,1);}
	for(int i=1;i<=n;i++){d[i]=read();P[d[i]]=make_pair(i,2);}
	for(int i=1;i<=n;i++){fa[a[i]]=b[i];fa[b[i]]=a[i];}
	for(int i=1;i<=n;i++)
	{
		if(fa[c[i]]!=d[i] || fa[d[i]]!=c[i]){puts("dldsgay!!1");return 0;}
		if((P[a[i]].first+P[a[i]].second)%2!=(i+1)%2){puts("dldsgay!!1");return 0;}
		if((P[b[i]].first+P[b[i]].second)%2!=(i+2)%2){puts("dldsgay!!1");return 0;}
	}
	for(int i=1;i<=n;i++)p[a[i]]=i;
	for(int i=1;i<=n;i++)c[i]=p[c[i]]+p[d[i]];
	long long ans=0;
	for(int i=n;i>=1;i--)
	{//树状数组求逆序对
		ans+=query(c[i]);
		add(c[i]);
	}
	printf("%lld\n",ans);
	return 0;
}