Codeforces Round #759 (Div. 2) D~F_随笔

Codeforces Round #759 (Div. 2) D~F D 题面

思路

首先要知道奇排列和偶排列的概念；

对一个数列，如果总的逆序数为奇数，则此排列为奇排列，否则为偶排列；

对于一次交换swap(i,j)来说，会改变排列的奇偶性，如下图；

而题目要我们执行swap(i,j)与swap(j,k);

也就是两次交换，因此排列的奇偶性不变；

因此，对于排列来说，我们只需要计算逆序对是奇还是偶，偶数则为YES，奇数则是NO；

因为这道题可能有重复的数字出现；

比如 [ 3 , 2 , 3 , 1 ] [3,2,3,1] [3,2,3,1]，下面两种换法是等价的；

我们可以设第一个3为 p p p，第二个3为 q q q，数字1为 r r r；

r → p r → p r→p
p → q p → q p→q
q → r q → r q→r

因为 p p p与 q q q数字是相等的，因此我们可以写成如下形式；

r → p r → p r→p
q → q q → q q→q
p → r p → r p→r

也就是说，如果出现了重复数字，则允许交换任意两个元素，那么必然是YES；

Code

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 5e5 + 10;

int a[N],tr[N];

int lowbit(int x){
    return x & -x;
}
void add(int u,int v){
    for(int i=u;i ve;
int get(int x){
    return 1 + lower_bound(ve.begin(),ve.end(),x) - ve.begin();
}
map mp;
void solve(){
    int n;
    cin >> n;
    for(int i=1;i<=n;++i) tr[i] = 0;
    mp.clear();
    ve.clear();
    for(int i=1;i<=n;++i){
        cin >> a[i];
        ve.push_back(a[i]);
        ++mp[a[i]];
    }
    sort(ve.begin(),ve.end());
    ve.erase(unique(ve.begin(),ve.end()),ve.end());
    for(auto x : mp){
        if(x.second > 1){
            cout << "YESn";
            return;
        }
    }
    int res = 0;
    for(int i=1;i<=n;++i){
        res += query(n) - query(get(a[i]));
        add(get(a[i]),1);
    }
    if(res & 1) cout << "NOn";
    else cout << "YESn";
}

signed main(){
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}

待补

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5713968.html

Codeforces Round #759 (Div. 2) D~F

发表评论

评论列表（0条）