交换如果相等长度和总和

Hint 1

尝试寻找不变量。

Hint 2

\texttt{Observation:}

交换后数组中所有 1 的位置下标和不变，且 1 的总个数不变。

尝试对于所有满足上述条件的

a,b

寻找操作方案，即证明充要。

Hint 3

操作次数的限制较为宽松，尝试每步使用形如 1000...000 和 000...0001 的操作归位一个 1，以此构造出操作次数

\leq n

的方案。

Hint 4

尝试对序列做一些变换使得操作次数

\leq \lfloor\frac{n}{2}\rfloor

。

Solution

先阅读所有提示。

显然操作不能改变 1 的个数。

发现操作不会改变所有 1 的下标和。证明是简单的，假设交换的区间为

[l,r]

和

[l',r']

且满足

r<l'

，那么交换过后

[l',r']

内每个 1 下标减少了

l'-l

，

[l,r]

内每个 1 下标增加了

l'-l

，故 1 的下标和相等。

合理猜测上述条件充要。尝试构造方案。

手搓几次操作，观察到操作长度为

2

的区间等价于将一个 1 向后挪一位，另一个 1 向前挪一位。于是不难想到一个思路，考虑每次操作归位一个 1，使用 000...0001 和 1000...000 进行操作，等价于一个 1 往后挪若干位，另一个 1 往前挪若干位。每次挑选一个 1 归位即可。

然而，上述做法操作次数最大可以达到

n

，需要优化。观察到当 1 的个数超过

\lfloor\frac{n}{2}\rfloor

时操作次数才有可能超出限制，而此时 0 的个数一定不超过

\lfloor\frac{n}{2}\rfloor

，故只需把原序列按位翻转即可。

于是，我们对于每一个满足 1 下标和相等且 1 数量相等的

a

和

b

都能构造出方案，即证明了其充要。

实现时，先判掉无解，然后将两序列的 1 一一匹配，分为往左挪和往右挪两类，一次挪一个即可。记得输出时，把靠右的区间输出在后面。

Code

CPP

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define _rep(i,a,b) for(int i=(a);i>=(b);i--)
#define pi pair<int,int>
#define arr(a) array<int,(a)>
#define F fflush(stdout)
#define RE return puts("No"),void()
#define cases(_) while((_)--) solve();
using namespace std;
const int N=200005;
int _=1,n,a[N],b[N],s;
vector<arr(3)> ans;
vector<pi> pre,suf;
vector<int> va,vb;
void solve(){
	scanf("%d",&n),s=0,ans.clear(),pre.clear(),suf.clear(),va.clear(),vb.clear();
	rep(i,1,n){
		scanf("%d",&a[i]);
		if(a[i]) va.push_back(i),s+=i;
	}
	rep(i,1,n){
		scanf("%d",&b[i]);
		if(b[i]) vb.push_back(i),s-=i;
	}
	int m=(int)va.size();
	if(m!=(int)vb.size() || s) RE;
	if(m>n/2){
		rep(i,1,n) a[i]^=1,b[i]^=1;
		va.clear(),vb.clear();
		rep(i,1,n){
			if(a[i]) va.push_back(i);
			if(b[i]) vb.push_back(i);
		}
		m=n-m;
	}
	m--;
	rep(o,0,m){
		if(va[o]<vb[o]) pre.push_back({va[o],vb[o]});
		else if(va[o]>vb[o]) suf.push_back({va[o],vb[o]});
	}
	int l=(int)pre.size()-1,r=0;
	while(l!=-1 && r!=(int)suf.size()){
		int pl=pre[l].second-pre[l].first,pr=suf[r].first-suf[r].second,cur=min(pl,pr);
		ans.push_back({pre[l].first,suf[r].first-cur,cur});
		pre[l].first+=cur,suf[r].first-=cur;
		if(pl==cur) l--;
		if(pr==cur) r++;
	}
	puts("Yes");
	printf("%d\n",(int)ans.size());
	for(arr(3) t:ans){
		if(t[0]+t[2]<t[1]) printf("%d %d %d %d\n",t[0],t[0]+t[2],t[1],t[1]+t[2]);
		else printf("%d %d %d %d\n",t[1],t[1]+t[2],t[0],t[0]+t[2]);
	}
}
signed main(){
	scanf("%d",&_);
	cases(_);
	return 0;
}

交换如果相等长度和总和

文章操作

相关推荐

评论

交换如果相等长度和总和