Codeforces Round 899 (Div. 2) E1. Two Permutations (Easy Version) (思维题/交换序列)

题目

长为n的序列a和长为m的序列b(n,m<=2500)

每次你需要输出两个下标i,j(1<=i<=n,1<=j<=m)，分别对两个序列执行以下交换操作

交换操作

不妨序列长度为n，选择下标为i，第二个序列类似

交换前，[1,i-1]、[i,i]、[i+1,n]

交换后，[i+1,n]、[i,i]、[1,i-1]

为了使得两个序列都有序，输出操作数及操作步骤（每次选的i、j下标），无解输出-1

easy version：不要求最小化操作数，10000次操作以内即可

hard version：要求最小化操作数

思路来源

tanao、syq学弟&uoj群

题解

感觉之前做过一个类似的交换序列的，好像也是3次，只是交换方式不一样

结论

两个序列，长度均为偶数时，逆序对数奇偶性不同时无解

否则一定有解，且每三步操作可以换任意两个数的位置，方式如下：

x x 1 2 3 4 y y，选中1所在位置交换

2 3 4 y y 1 x x ，选中4所在位置交换

y y 1 x x 4 2 3，选中1所在位置交换

x x 4 2 3 1 y y，三步交换了1、4两数所在位置

证明

以下证明来自uoj群

不妨称[1,i-1],i,[i+1,n]三段为b,a,c，

1. 操作后b和c之间的逆序对数=操作前b和c的顺序对数=|b|*|c|-操作前b和c的逆序对数

由于|b|+|c|=n-1为奇数，则|b|*|c|一定为偶数，则b、c之间的逆序对数操作前后奇偶性不变

2. 操作后a和bc的逆序对数=操作前a和bc的顺序对数=|b|+|c|减去操作前a和bc中的逆序对数，

由于|b|+|c|=n-1为奇数，则a和bc之间的逆序对数操作前后奇偶性改变

综上，n是偶数时，每一步操作，都会改变逆序对数的奇偶性

后半部分

假设用了a步将第一个序列换成有序的，b步将第二个序列换成有序的

1. 如果a和b的奇偶性相同，由于选中一个值连换两次等于什么都没操作，所以可以凑足次数

2 1 3，选中1所在位置交换

3 1 2，选中1所在位置交换

2 1 3

2. 如果a和b奇偶性不同，由于序列长度有一个是奇数，可以操作n次改变奇偶性，转变为1的情形

2 1 3，选择3所在位置交换

3 2 1，选择1所在位置交换

1 3 2，选择2所在位置交换

2 1 3

代码

代码强行精简了一波，统一这若干种情况，避免若干讨论

#include
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define dbg(x) cerr<<(#x)<<":"<" ";
#define dbg2(x) cerr<<(#x)<<":"<
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pb push_back
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
std::mt19937_64 gen(std::chrono::system_clock::now().time_since_epoch().count());
ll get(ll l, ll r) { std::uniform_int_distribution dist(l, r); return dist(gen); }
const int N=2510;
int n,m,a[N],b[N],pos[N];
vector<int>swp(int *c,int k){
	vector<int>ans;
	rep(i,1,k)pos[c[i]]=i;
	rep(i,1,k){
		if(pos[i]==i)continue;
		int x=i,y=pos[i],v=c[i];
		ans.pb(x);
		ans.pb(y-x);
		ans.pb(k-y+1);
		pos[v]=y;
		c[y]=v;
	}
	return ans;
}
void sol(){
	vector<int>l=swp(a,n),r=swp(b,m);
	int u=n%2,v=m%2,w=(SZ(r)-SZ(l))%2;
	if(w){
		if(!u && !v)return (void)puts("-1");
		if(u)rep(i,1,n)l.pb(1);
		else if(v)rep(i,1,m)r.pb(1);
	}
	while(SZ(l)<SZ(r))l.pb(1),l.pb(n);
	while(SZ(r)<SZ(l))r.pb(1),r.pb(m);
	int k=SZ(l);
	pte(k);
	rep(i,0,k-1){
		printf("%d %d\n",l[i],r[i]);
	}
}
int main(){
	sci(n),sci(m);
	rep(i,1,n)sci(a[i]);
	rep(i,1,m)sci(b[i]);
	sol();
	return 0;
}