2019-2020 10th BSUIR Open Programming Championship. Semifinal

GYM链接https://codeforces.com/gym/103637

K

题意：

给定\(n\)个二进制下不超过\(m\)位的数，找到一个二进制下不超过\(m\)位且至多有\(k\)个\(1\)的最小的数\(X\)，使得最大化\(\sum_{i=1}^nmax(a_i,a_i\)^\(X\)).

思路：

赛时看到本题的第一想法是贪心。从高位到低位，依次统计每一位的0和1的数量，然后最大化收益决定此位是0还是1。但思考后发现这显然不成立，虽然对于此位置独立收益最大，但根本没有考虑得到的\(X\)和每个数异或后是原来的数大还是异或后的数大。
本题正确的思路应是这样：考虑到\(k\)的取值最大只有30，我们可以进行暴力枚举。初始我们令初始答案为\(0\)，至多只能有\(k\)个数从\(0\)变成\(1\)，我们可以计算出在当前答案下的\(\sum_{i=1}^nmax(a_i,a_i\)^\(X\)) 的值，然后从低到高枚举哪一位可以从\(0\)变成\(1\)，设第\(q\)位可以从\(0\)变成\(1\)，那么\(q\)就等于在取得:
\(\max_{0 \leq j <m} \left\{\begin{matrix}\sum_{i=1}^n max(a_i,a_i xorX)<\sum_{i=1}^nmax(a_i,a_ixor(X+(1<<j)))\end{matrix}\right\}\)下的\(j\)。
如果一次循环完没有一位可以满足要求，那就表示当前的答案已经是最终答案，输出即可。时间复杂度\(O(kmn)\)。

代码：

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define ywh666 std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

#define all(a) a.begin(),a.end()

typedef long long ll ;

int main(){

        ywh666;

    ll n, m, k;

    cin >> n >> m >> k ;

    vector<ll> a(n);

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

        cin >> a[i];

    }

    ll ans = 0 ;

    for(int i = 0 ; i < k ; i ++){

        ll sum = 0 ;

        ll f = -1 ;

        for(int j = 0 ; j < n ; j ++){

            sum += max(a[j], a[j] ^ ans);

        }

        for(int j = 0 ; j < m ; j ++){

            if(ans & (1ll << j)) continue;

            ll cnt = 0;

            for(int k = 0 ; k < n ; k ++){

                cnt += max(a[k], a[k] ^ (ans + (1ll << j)));

            }

            if(cnt > sum){

                f = j;

                sum = cnt;

            }

        }

        if(f != -1){

            ans += (1ll << f);

        }else{

            break;

        }

    }

    cout << ans << endl;

}

巴特西

2019-2020 10th BSUIR Open Programming Championship. Semifinal

2019-2020 10th BSUIR Open Programming Championship. Semifinal

GYM链接https://codeforces.com/gym/103637

K

题意：

思路：

代码：

最新文章

热门文章