【bitmask】CF731div3 D

谁践踏了优雅 2024-03-27 13:53 76阅读 0赞

**这道题赛后秒了，是个结论（感觉也不算，因为非常好推）**

**感觉这种序列+bitmask就是把这个序列想象成一个01矩阵，横向是30位的bit，纵向是n个数，这样感觉会好想一点，如果序列不是有序的话直接用30位的桶记录一下就好了**

[Problem - D - Codeforces][]

题意：

给定一个ai序列，让你构造出一个bi序列，使得ai^bi得到的ci满足 c\[i\]&c\[i+1\]==c\[i\]

其中bi必须满足字典序最小

思路：

首先对于c\[i\]&c\[i+1\]==c\[i\]这个条件可以直接转化为：

对于纵向的两行，不存在1 0，其中1在上一行，0在下一行

这个结论很好想，4种情况分类讨论就行了

所以我们要用异或消除所有的上下的1 0对

这样构造出来的bi是不唯一的。那么我们怎么去保证它的字典序最小呢？

举个例子，比如说：

我们可以用：

0 0 1

0 1 1

来消除1 0对

然后要让字典序最小，就要让1的贡献尽可能靠后，所以异或数组选0 1最合适

所以我们用途0 1把1 0变成1 1

Code：

#include <bits/stdc++.h>
    #define int long long
    #define y1 Y1
    const int mxn=2e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    const int Mnf=1e18;
    const int Inf=-1e18;
    using namespace std;
    
    
    int n;
    int a[mxn],b[mxn],c[mxn];
    void solve(){
        memset(b,0,sizeof(b));
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n-1;i++){
            for(int j=30;j>=0;j--){
                if(((a[i]>>j)&1)==1&&((a[i+1]>>j)&1)==0){
                    a[i+1]|=(1<<j);
                    b[i+1]|=(1<<j);
                }
            }
        }
        //for(int i=1;i<=n;i++) c[i]=a[i]^b[i];
        for(int i=1;i<=n;i++) cout<<b[i]<<" \n"[i==n];
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problem - D - Codeforces]: https://codeforces.com/contest/1547/problem/D