首页 > 其他分享 >Atcoder ABC296 F

Atcoder ABC296 F

时间:2024-07-31 11:07:34浏览次数:17  
标签:Atcoder h1 th int 元素 tr 数组 ABC296

Atcoder ABC296 F

F - Simultaneous Swap

链接:

F - Simultaneous Swap (atcoder.jp)

简要题意:

  • 问题陈述

    给你两个 \(N\) 数字序列: \(A=(A_1,A_2,\ldots,A_N)\) 和 \(B=(B_1,B_2,\ldots,B_N)\) 。

    高桥可以重复下面的操作任意多次(可能为零)。

    在 \(1\) 和 \(N\) 之间选择三个成对的不同整数 \(i\) 、 \(j\) 和 \(k\) 。
    把 \(A\) 的 \(i\) -th 和 \(j\) -th 元素对调,把 \(B\) 的 \(i\) -th 和 \(k\) -th 元素对调。

    如果高桥有办法重复操作使 \(A\) 和 \(B\) 相等,打印 "Yes";否则,打印 "No"。
    在这里, \(A\) 和 \(B\) 相等的条件是,对于每一个 \(1\leq i\leq N\) , \(A\) 的 \(i\) 个元素和 \(B\) 的 \(i\) 个元素相等。

思路:

  • 首先a与b数组元素不相同的情况下一定是NO

  • 我们发现一个重要性质,我们可以保持A不动,只改变B,操作如下

  • 我们发现b数组可以循环轮换排列,并且,如果b数组或者a数组有两个相同元素,那么她们可以通过反复横跳使得顺序一致

  • 如果两个数组中分别都没有重复元素

  • 我们考虑一次上图循环置换顺序,只会让逆序对+2,0,-2,这就意味着奇偶性相同ab数组一定可以转换,反之则不能

代码:

const int N = 200005;
int tr1[N],tr2[N];
int n;
int lb(int x){return x&-x;}
void add(int k,int tr[]){
    for(int i = k;i < N;i+=lb(i)) tr[i]++;
}
int qy(int k,int tr[]){
    int res = 0;
    for(int i = k;i > 0;i-=lb(i)) res+=tr[i];
    return res;
}
void solve(){
    
    cin >> n;
    map<int,int> h1;
    map<int,int> h2;
    int a[n + 1],b[n+1];
    int c1 = 0,c2 = 0;
    for(int i = 1;i<=n;i++){
        cin >> a[i];
        c1+=qy(a[i],tr1);
        add(a[i],tr1);
        h1[a[i]]++;
        
    }
    for(int i = 1;i<=n;i++){
        cin >> b[i];
        c2+=qy(b[i],tr2);
        add(b[i],tr2);
        h2[b[i]]++;
        
    }
    if(h1!=h2){
        cout << "No" << endl;
        return ;
    }
    for(int i = 1;i<=n;i++){
        if(h2[b[i]]>=2||h1[a[i]]>=2){
            cout << "Yes" << endl;
            return;
        }
    }
    if(c1%2!=c2%2){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
 
}

标签:Atcoder,h1,th,int,元素,tr,数组,ABC296
From: https://www.cnblogs.com/bananawolf/p/18334203

相关文章

  • Atcoder 356 C - Keys 二进制枚举
    原题链接:https://atcoder.jp/contests/abc356/tasks/abc356_c C-Keys:问题陈述您有 N 个编号为1,2,…,N 的密钥。其中一些是真钥匙,其他都是假钥匙。有一扇门,门X,你可以插入任意数量的钥匙。只有插入至少 K 把真钥匙,X门才会打开。你已经对这些钥匙进行了 M 次......
  • Solution - Atcoder APC001E Antennas on Tree
    首先考虑判定什么样的选取是合法的。考虑到令任意一个点\(u\)为根。若\(u\)有至少两个子树没有点选中,那么这两个子树是无法区分的。所以可以知道需要满足任意一个点为根,都至多存在一个子树内部没有选中的点。接下来就要贪心的选出最少的点了。考虑对于每个点的限制都是子......
  • Solution - Atcoder AGC028B Removing Blocks
    因为贡献的方法是相加,一种想法就是拆开,对每一项单独贡献。不难发现这题目中的贡献其实只涉及到两点之间。即删除\(x\)时\(y\)也产生了贡献。考虑这个贡献会在多少种排列中出现。令\(d=|x-y|+1\),即\(x,y\)中的点数。能发现排列需要满足除\(x\)外的\(d-1\)......
  • Atcoder ABC364 D-F
    AtcoderABC364D-FD-K-thNearest链接:D-K-thNearest(atcoder.jp)简要题意:问题陈述在一条数线上有\(N+Q\)个点\(A_1,\dots,A_N,B_1,\dots,B_Q\),其中点\(A_i\)的坐标为\(a_i\),点\(B_j\)的坐标为\(b_j\)。请就每个点\(j=1,2,\dots,Q\)回答下面的问题:......
  • Solution - Atcoder YPC2019E Odd Subrectangles
    首先对于\(0/1\)和为奇数,转化为异或为\(1\)来考虑。考虑如果已经确定了行的选取,又该如何计数。考虑对于每一列,都处理好在对应行的位置的异或值。然后记\(\operatorname{c}_0,\operatorname{c}_1\)表示列异或值为\(0/1\)的数量。知道了\(\operatorname{c}_0,\op......
  • Solution - Atcoder UTPC2023P Priority Queue 3
    考虑找一些关于合法的\(X\)加入的数的判定条件。假设遇到了一个\(\operatorname{pop}\)操作,令这里删除的数为\(a_i\),显然\(X\)中的数应该要有\(a_i\),其次\(X\)中其他的加入的数要么\(>a_i\)要么是\(a\)中的元素(在前面的\(\operatorname{pop}\)就已经被删了)。于......
  • AtCoder Beginner Contest 362
    AtCoderBeginnerContest362前言vp的时候出了四题,被C题卡了一会,很久才出,D题是dijkstra的板子,改下条件即可,E题是个计数dp,这类题一直不怎么擅长,想起之前杭电第一场那个序列立方的题也是类似这种计数dp,需要加强练习。A-BuyaPen(atcoder.jp)思路判断两两最小。......
  • Solution - Atcoder ABC280Ex Substring Sort
    对于这种子串问题,且有多个基础串,一个比较直观的想法就是先上个广义SAM。考虑SAM与字典序如何联系上。因为跳\(\operatorname{fail}\)相当于是删除子串的一个前缀,直接这样子明显是不行的,因为跳了\(\operatorname{fail}\)字典序没有一个很直观地表示。但是反过来考虑反串,......
  • Solution - Atcoder ARC114F Permutation Division
    令\(a\)为题目中的\(P\)。首先考虑后手的重排策略是什么。因为\(a\)是个排列,元素互不相同,那么肯定就是按照每一段的第一个数的大小,越大的放在越前面。那么当\(a_1\lek\)的时候,显然先手会把以\(1\simk\)开头来划分段。因为否则存在一个开头\(>k\)的段,后手把其放......
  • AtCoder Beginner Contest 363 题解 A-D(待补充)
    A-PilingUp1.1思路其实就是向上取百位的整,需要增加多少,123则为200-123=177;1.2代码voidsolve(){intn;cin>>n;intt=n/100;cout<<(t+1)*100-n;}B-JapaneseCursedDoll 2.1思路就是判断最少需要多少天,会有大于等于P个人......