题解：CF2254F Whiplash

fish_love_cat · 2026-08-10 08:40:32 · 题解

考虑拆位，然后统计每个位 \texttt{01} 的出现次数。

对于一个位，我们假设在数列 a 中 \texttt1 出现了 x_1 次，那么 \texttt0 就是 n-x_1 次。对称的我们定义 x_2 是在 b 里的出现次数。

分讨一下，我们发现如果 x_1=x_2，那么这一位必然异或 \texttt0；如果 x_1+x_2=n+1，那么这一位必然异或 \texttt1。其余情况显然无解。

于是我们就得到了正常情况下拿来异或的数。

首先两个集合里都得有这个数，先踢出去。然后对其中一个集合依次异或一遍判断能不能生成另一个集合，做完了。

用 map 开桶复杂度变成了 O(n\log n)。

int a[200005];
int b[200005];
int s1[30],s2[30];
inline void solve(){
    memset(s1,0,sizeof s1);
    memset(s2,0,sizeof s2);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        for(int j=0;j<30;j++)
        if(a[i]&(1<<j))
        s1[j]++;
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        for(int j=0;j<30;j++)
        if(b[i]&(1<<j))
        s2[j]++;
    }
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    bool qwq=1;
    for(int i=1;i<=n;i++){
        if(a[i]!=b[i])qwq=0;
    }
    if(qwq){
        cout<<"Yes\n";
        return;
    }
    int flc=0;
    for(int i=0;i<30;i++)
    if(s1[i]+s2[i]==n+1)flc+=1<<i;
    else if(s1[i]==s2[i])flc+=0;
    else{
        cout<<"No\n";
        return;
    }
    map<int,int>mp;
    for(int i=1;i<=n;i++)
    mp[a[i]]++;
    if(!mp[flc]){
        cout<<"No\n";
        return;
    }
    mp[flc]--;
    bool flg=1;
    for(int i=1;i<=n;i++)
    if(flg&&flc==b[i])flg=0;
    else mp[b[i]^flc]--;
    for(auto i:mp)
    if(i.second){
        cout<<"No\n";
        return;
    }
    cout<<"Yes\n";
}
// 恳求 沉默的宇宙
// 借我 十秒的回眸
// 让我 再拥抱最后
// 时间 碎在相扣的心头