牛客练习赛107 D 补天裂

拼搏现实的明天。 2024-03-30 13:16 56阅读 0赞

[D-补天裂\_牛客练习赛107 (nowcoder.com)][D-_107 _nowcoder.com]

题意：

![94c848d393574d259e65c63771d844cb.png][]

思路：

一开始想的是越与越小，越或越大

所以去从前往后

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e5+10;
    int n;
    int a[mxn];
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                int t=a[i];
                a[i]&=a[j];
                a[j]=t|a[j];
            }
        }
        for(int i=1;i<=n;i++) cout<<a[i]<<" ";
        cout<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

这样还过了两个样例，还以为这样是对的

这样显然是错的，因为与了后面的之后也可以与前面的，因此是错误的

正解是：

不论怎么操作，每一位1的个数和0的个数是不变的

因此我们可以贪心地从后往前去赋1

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e5+10;
    int n,x;
    int bit[40];
    int a[mxn];
    void solve(){
        memset(bit,0,sizeof(bit));
        memset(a,0,sizeof(a));
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>x;
            for(int j=30;j>=0;j--){
                if((x>>j)&1) bit[j]++;
            }
        }
        for(int i=n;i>=1;i--){
            for(int j=30;j>=0;j--){
                if(bit[j]){
                    a[i]+=(1<<j);
                    bit[j]--;
                }
            }
        }
        for(int i=1;i<=n;i++) cout<<a[i]<<" \n"[i==n];
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

**总结：**

**a\[i\]&=a\[j\]**

**a\[j\]|=a\[i\]**

**这样的操作，每一位1的总个数和0的总个数不变**

[D-_107 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/49035/D
[94c848d393574d259e65c63771d844cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7384623967cf448c908d98a91e5bcc67.png