题目链接:https://atcoder.jp/contests/abc296/tasks/abc296_f
思维题,自己想的时候真没啥思路,看了很多题解才渐渐明白,也能大致证明正确性。
前置知识:
交换一个排列中的两个元素一次,会改变它的奇偶性。
思路:
1.当两个数组的数的数量都不相等时,肯定是不能使得他们相等的。
2.当数组中有两个或两个以上相同的数,一定可以证明有交换方式使得他们相等。
3.当数组中每个数只出现一次时,只有他们奇偶性相同时才能使得相等。
思路2证明(大致):
假设我有一个排列1,1,3为A,而B为3,1,3,我每次只选定A的1号位和2号位交换,而B每次可以选择1,3和2,3进行交换,易得B可以变换到它的所有排列,得证。
思路3证明(大致):设A排列为1,2,3,B排列为2,1,3,我每次只选定A的1号位和2号位交换,而B每次可以选择1,3和2,3进行交换,每换一次A与B的奇偶性都会改变,通过这样的(偶数次)方式交换,我可以得到B的所有奇排列或偶排列(取决于B的奇偶性)。得证。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int tr[N];
int a[N],b[N];
int lowbit(int x){
return x&-x;
}
void add(int x){
for (int i=x;i<=200000;i+=lowbit(i)) tr[i]++;
}
int query(int x){
int res = 0;
for (int i=x;i>=1;i-=lowbit(i)) res += tr[i];
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
bool flag = 1,flag1 = 0;
int ia = 0,ib = 0;
for (int i=1;i<=n;i++){
int x;
cin>>x;
a[x]++;
if (a[x]>=2) flag1 = 1;
ia += (query(n)-query(x));
add(x);
}
memset(tr,0,sizeof(tr));
for (int i=1;i<=n;i++){
int x;
cin>>x;
a[x]--;
ib += (query(n)-query(x));
add(x);
}
for (int i=1;i<=n;i++){
if (a[i]) flag = 0;
}
if (!flag) cout<<"No\n";
else if (flag1) cout<<"Yes\n";
else if (((ia+ib)&1)) cout<<"No\n";
else cout<<"Yes\n";
return 0;
}
标签:int,号位,tr,奇偶性,query,abc296
From: https://www.cnblogs.com/xjwrr/p/17287382.html