C/C++教程

Educational Codeforces Round 134 D

本文主要是介绍Educational Codeforces Round 134 D,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

D. Maximum AND

可以很轻松通过^和& 两个操作看出 我们要求的两个序列每一位上的1加起来必须等于n才行
多一个少一个都不行
然后1加起来等于n 0自然加起来也等于n 0和1的数量相等
但是直接每一位算肯定是不对的 因为会有有些组不同 比如样例1
我们考虑按位贪心 让后面的组要是和前面组符合 那么加入即可
这里就可以用map 要是后面的组符合前面的组 那么我们就算加上了1<<j也依然符合才行

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int M = 998244353;
const int mod = 1000000007;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++)cin >> a[i];
    for (int i = 0; i < n; i++)cin >> b[i];
    int c = 0;
    for (int j = 29; j >= 0; j--) {
        map<int, int> mp;
        c += 1 << j;
        for (int i = 0; i < n; i++) {
            mp[a[i] & c]++;
            mp[~b[i] & c]--;
        }
        bool flag = true;
        for (auto i: mp) {
            if (i.second != 0) {
                flag = false;
                break;
            }
        }
        if (!flag) c -= (1 << j);
    }
    cout << c << endl;
}
signed main(){
    fast
    int T;cin>>T;
    while(T--) {
        solve();
    }
    return ~~(0^_^0);
}
这篇关于Educational Codeforces Round 134 D的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!