Codeforces Round #827 (Div. 4) G. Orray

逃离我推掉我的手 2024-03-29 14:57 91阅读 0赞

[Problem - G - Codeforces][]

题意：

给定一个数列，让你重新排列这个数列，使得其前缀或最大

思路：

贪心策略就是找一个与pre或起来最大的值

重点是怎么写呢

感觉div4的题思路都很简单，难的就是写法qwq

我的写法是从高位到低位遍历，出现a\[i\]该位是1，pre该位是0的时候就选a\[i\]

然后写了一坨答辩，然后果不其然WA2了，好死

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e5+10;
    map<int,int> mp;
    vector<int> v[65],ans;
    int n,ansit,ok=0;
    int a[mxn],cnt[mxn];
    void solve(){
        memset(cnt,0,sizeof(cnt));
        ans.clear();
        mp.clear();
        ok=0;ansit=0;
        bitset<32> pre;
        for(int i=30;i>=0;i--) v[i].clear();
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i],mp[a[i]]++;
            for(int j=30;j>=0;j--){
                if((a[i]>>j)&1) cnt[j]++,v[j].push_back(a[i]);
            }
        }
        for(int j=30;j>=0;j--){
            if(pre[j]==0&&cnt[j]>=1){
                //cout<<pre[j]<<" "<<cnt[j]<<'\n';
                for(auto it:v[j]){
                    //cout<<it<<" "<<j<<'\n';
                    for(int k=j-1;k>=0;k--){
                        int ansk,mx=-1;
                        ok=0;
                        if(pre[k]==0&&((it>>k)&1)&&!ok){
                            ok=1;
                            ansk=k;
                            //cout<<ansk<<'\n';
                        }
                        if(ansk>mx){
                            mx=ansk;
                            ansit=it;
                        }
                    }
                }
                if(!ok){
                    sort(v[j].begin(),v[j].end());
                    ansit=v[j][0];
                }
                if(!ansit) continue;
                ans.push_back(ansit);
                mp[ansit]--;
                for(int k=30;k>=0;k--){
                    if((ansit>>k)&1) pre[k]=1,cnt[k]--;
                }
            }
            /*if(j>3) continue;
            for(int k=3;k>=0;k--) cout<<pre[k]<<" \n"[k==0];
            for(int k=3;k>=0;k--) cout<<cnt[k]<<" \n"[k==0];
            cout<<'\n';*/
        }
        sort(a+1,a+1+n);
        for(int i=1;i<=n;i++){
            if(mp[a[i]]) ans.push_back(a[i]),mp[a[i]]--;
        }
        for(int i=0;i<ans.size();i++) cout<<ans[i]<<" \n"[i==ans.size()-1];
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

懒得找哪里错了

（1.31更：现在找到了，是贪心策略的问题，这个每一阶段该选哪个是不能直接按位去贪心的，因为位高的一个1不一定比位小的好几个1来的大，所以我们贪心时应该计算一下贡献，这道题肯定得暴力去判断的）

跑去看jiangly代码

不得不说他的代码写的确实简洁啊

就是去暴力统计哪个a\[i\]或上pre最大，然后选上最大值就行了

n^2是能跑过2000ms的

看了他的代码才发现时限是2000ms，嘻

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=2e5+10;
    vector<int> v;
    int n,cur;
    int a[mxn],vis[mxn];
    void solve(){
        cur=0;
        v.clear();
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],vis[i]=0;
        for(int i=1;i<=n;i++){
            int mx=0,ansi=-1;
            for(int j=1;j<=n;j++){
                if((a[j]&(~cur))>mx&&!vis[j]){
                    mx=a[j]&(~cur);
                    ansi=j;
                }
            }
            if(ansi<0) break;
            v.push_back(a[ansi]);
            vis[ansi]=1;
            cur|=a[ansi];
        }
        for(int i=1;i<=n;i++){
            if(!vis[i]) v.push_back(a[i]);
        }
        for(int i=0;i<v.size();i++) cout<<v[i]<<" \n"[i==v.size()-1];
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

好丑的代码，感觉不如jiangly：

#include <bits/stdc++.h>
    
    using i64 = long long;
    
    void solve() {
        int n;
        std::cin >> n;
        
        std::vector<int> a(n);
        for (int i = 0; i < n; i++) {
            std::cin >> a[i];
        }
        std::vector<int> b;
        std::vector<bool> vis(n);
        
        int cur = 0;
        for (int i = 0; i < n; i++) {
            int mx = 0, k = -1;
            for (int j = 0; j < n; j++) {
                int x = a[j] & ~cur;
                if (!vis[j] && x > mx) {
                    mx = x;
                    k = j;
                }
            }
            if (k < 0) {
                break;
            }
            vis[k] = true;
            b.push_back(a[k]);
            cur |= a[k];
        }
        
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                b.push_back(a[i]);
            }
        }
        for (int i = 0; i < n; i++) {
            std::cout << b[i] << " \n"[i == n - 1];
        }
    }
    
    int main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        
        int t;
        std::cin >> t;
        
        while (t--) {
            solve();
        }
        
        return 0;
    }

[Problem - G - Codeforces]: https://codeforces.com/contest/1742/problem/G