CF2147E 题解

赛时想了个二分做法假飞了，最后遗憾离场了。/dk

Solution

考虑求出对于每个答案，需要的最小操作数。

把不操作时所有元素的按位或结果记作 $c$，显然小于 $\text{popcount}(c)$ 的答案都是 $0$。然后考虑从 $c$ 往上增加，首先显然为了让操作数较小，我们要优先让低位的 $0$ 变成 $1$。设我们要让第 $0 \sim m$ 位都变成 $1$，会发现从第 $m$ 位开始依次变 $1$ 是最优的，因为低位变 $1$ 不会影响高位而高位变 $1$ 会影响低位，把第 $s$ 位加到 $1$ 的结果必然会变成 $\texttt{...xxxx10000... }$ 这样第 $s$ 位以下都会变成 $0$，之前的操作就白费了，所以从高位往低位操作是更优的。于是按照上面的策略，模拟操作即可。

Code

// Problem: CF2147E Maximum OR Popcount
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF2147E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long 
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define rep(i, a, b) for(int (i) = (a); (i) <= (b); (i) ++)
#define per(i, a, b) for(int (i) = (a); (i) >= (b); (i) --)
#define REP(i, l, r, k) for (int i = (l); i <= (r); i += k)
#define PER(i, l, r, k) for (int i = (l); i >= (r); i -= k)
#define ls x << 1
#define rs x << 1 | 1
#define umap unordered_map
#define uset unordered_set
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define x1 Sun
#define y1 Jude
void ckmin(int &x, int y) { x = std::min(x, y) ; }
void ckmax(int &x, int y) { x = std::max(x, y) ; }
int lowbit(int x) { return x & -x ; }

using namespace std;

const int maxn = 1e5 + 5 ;
// const int inf = ;
// const int mod = ; 

int n, q, a[maxn] ;
int t[maxn] ;
int ans[35] ;

int calc(int x) {
    rep(i, 1, n) {
        t[i] = a[i] ;
    }
    int res = 0  ;
    per(s, x, 0) {
        int tg = 1ll << s, cnt = 2e9, id = 0 ;
        rep(i, 1, n) {
            int tmp = t[i] % (1ll << (s + 1)) ;
            if(max(tg - tmp, 0ll) < cnt) {
                cnt = max(tg - tmp, 0ll) ;
                id =  i ;
            }
        }
        res += cnt ;
        t[id] += cnt ;
    }
    return res ;
}

void solve(){
    rep(i, 0, 31) ans[i] = 0 ;
    cin >> n >> q ;
    int cur = 0 ;
    rep(i, 1, n) {
        cin >> a[i] ;
        cur |= a[i] ;
    }
    int pc = __builtin_popcount(cur) ;
    int m = 0 ;
    rep(i, 1, 31 - pc) {
        while((cur >> m) & 1) m ++ ;
        ans[i + pc] = calc(m) ;
        m ++ ;
    }
    while(q -- ) {
        int b ; cin >> b ;
        int x = upper_bound(ans, ans + 32, b) - ans  - 1 ;
        cout << x << endl ;
    }
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1 ; 
    cin >> T ;
    while(T -- ){
        solve() ;
    }
    return 0 ;
} 

---

• 分类： OI
• 标签： 无标签