ToB企服应用市场:ToB评测及商务社交产业平台

标题: Educational Codeforces Round 134 (Div.2) D 题解 [打印本页]

---

作者: 大连密封材料    时间: 2023-12-1 02:56
标题: Educational Codeforces Round 134 (Div.2) D 题解
题目链接

D. Maximum AND
题目大意

给定两组序列 \(a\) \(b\),长度为 \(n\) ，现有一新序列 \(c\)，长度也为 \(n\) 。
其中，\(c_i = a_i \oplus b_i\) 。
定义 \(f(a,b) = c_1\&c_2\&……\&c_n\)。
现在你可以随意编排 \(b\) 序列的顺序，求 \(f(a,b)\) 的最大值。
思路

以下位运算均是二进制。
由于按位与的运算结果是越来越小的，考虑从高位往低位贪心。
将结果的其中一位定为1之后，有一些序列 \(b\) 中的元素的位置就被定下来了。
所以我们要从高位往低位贪心，有一位可以置为1，就把它置为1.
具体做法：暴力枚举，时间复杂度\(O(nlognlogA)\)，其中 \(A\) 是输入序列的最大值。
[code]void solve() {        cin >> n;        a = vector (n);        b = vector (n);        for (int i = 0; i < n; ++i) {                cin >> a;        }        for (int i = 0; i < n; ++i) {                cin >> b;        }                auto check = [&](int ans){                //ans是一个2的整次幂                map cnt;                //下面两个for是 判断该位上、a序列的1和b序列的0的个数是否相等。                for(auto x:a) cnt[x & ans] += 1;                for(auto x:b) cnt[~x & ans] -= 1;                bool ok = true;                //如果有1，证明不等，ok置为false                for(auto [u,v] : cnt){                        ok &= v == 0;                }                return ok;        };                int ans = 0;        for(int j = 30; j >= 0; --j){                //从高位向低位检查。                //写博客的时候的思考：如何把之前的已经确定了的1保存下来                //答：其实就保存在ans中。                if(check(ans | (1ll

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4