CF1742G Orray

思路

大抵算是一道位运算入门题？

首先为了使 \(b_i\) 的字典序最大，我们注意到 \(b_1=a_1\)，所以 \(a_1\) 必然是序列中最大的那个数。

接下来考虑贪心，设当前已经填了 \(k\) 个数，此时的或和为 \(a\)，则我们从大往小扫，若 \(maxx\) 的第 \(i\) 位为 \(0\)，则接下来我们最好凑出 \(1\) 来，因为 \(2^i>\sum_{j=1}^{i-1} 2^j\)，如果实在凑不出来则 skip，如此贪心即可。

代码

#include<bits/stdc++.h>

using namespace std;

int const N=2e5+10;

int a[N],b[N],c[N],n,vis[N],k;

vector<int>q[50];

inline void chk(int &maxx,int id){

    int mxp=0,maxn=maxx;

    for (auto i:q[id]){

        if (vis[i]) continue;

        if ((a[i]|maxx)>maxn) maxn=(a[i]|maxx),mxp=i;

    }

    if (!mxp) return;

    c[++k]=a[mxp];vis[mxp]=1;

    maxx|=a[mxp];

    return;

}

inline void chk(int x){for (int i=30;~i;--i) if (a[x]&(1<<i)) q[i].push_back(x);}

signed main(){

    ios::sync_with_stdio(false);

    cin.tie(0),cout.tie(0);

    int t;cin>>t;

    while (t--){

        int maxx=0,mxp;cin>>n;

        for (int i=30;~i;--i) q[i].clear();k=0;

        for (int i=1;i<=n;++i) vis[i]=0;

        for (int i=1;i<=n;++i){

            cin>>a[i],chk(i);

            if (a[i]>maxx) maxx=a[i],mxp=i;

        }

        vis[mxp]=1;c[++k]=maxx;

        for (int i=30;~i;--i)

            if (!(maxx&(1<<i)) && q[i].size()) chk(maxx,i);

        for (int i=1;i<=k;++i) cout<<c[i]<<' ';

        for (int i=1;i<=n;++i) if (!vis[i]) cout<<a[i]<<' ';

        cout<<'\n';

    }

    return 0;

}

巴特西

CF1742G Orray

思路

代码

最新文章

热门文章