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

Codeforces Round #759 (Div. 2) D~F,第1张

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;
}
E

待补

F

待补

欢迎分享,转载请注明来源:内存溢出

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

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存