首页 > 其他分享 >Educational Codeforces Round 134 (Rated for Div. 2) D Maximum AND

Educational Codeforces Round 134 (Rated for Div. 2) D Maximum AND

时间:2022-09-02 14:33:37浏览次数:79  
标签:Educational Rated int Codeforces cin 排序 include Maximum

Maximum AND

贪心

从高位开始,尽可能地让 \(a\) 中该位为 \(0\) 的 和 \(b\) 中该位为 \(1\) 的配对在一起,换句话说,可以让 \(a\) 由小到大排序,\(b\) 由大到小排序

  • 如果当前位最终是 \(1\),则继续该过程

  • 如果当前位最终是 \(0\),则说明失配,考虑将这一位全部置为 \(1\) (排除这一位对排序造成的影响),重新排序

整个过程有种递归的感觉

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;

bool cmp(int a, int b)
{
    return a > b;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        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];
        sort(a.begin(), a.end());
        sort(b.begin(), b.end(), cmp);
        ll ans = 0;
        for(int i=30; i>=0; i--)
        {
            int f = (1 << 31) - 1;
            for(int j=0; j<n; j++)
                f &= a[j] ^ b[j];
            if(f >> i & 1 ^ 1)
            {
                for(int j=0; j<n; j++)
                {
                    a[j] |= 1 << i;
                    b[j] |= 1 << i;
                }
                sort(a.begin(), a.end());
                sort(b.begin(), b.end(), cmp);
            }
            else
                ans |= 1 << i;
        }
        cout << ans << "\n";
    }
    return 0;
}

标签:Educational,Rated,int,Codeforces,cin,排序,include,Maximum
From: https://www.cnblogs.com/dgsvygd/p/16649762.html

相关文章

  • codeforces极简题解
    CF1713F利用lucas定理,\(b_S\)表示下标\(T\)与\(S\)无交的\(a_T\)的异或,由于部分\(b_S\)未知,不能直接iFWT。回顾容斥:\([S=\emptyset]=\sum_{T\subseteqS}(-1)^|T|\),\([n=0......
  • Codeforces Round #773 E
    AnonymityIsImportant我们最开始会想到用三个状态表示其实并不用我们只需要用0表示这个人没病1表示不确定有病(这样我们就可以用set来做了)要是一个区间给了有病我们......
  • Educational Codeforces Round 134 (Rated for Div. 2)
    DMaxiumAnd贪心,优先满足高位,每次判断是否能够满足这一位答案为1,如果能则更新答案,这样显然是优的EPrefixFunction模仿求前缀函数的算法,先预处理求出\(|S|\)的前缀函......
  • Educational Codeforces Round 134 (Rated for Div. 2)
    EducationalCodeforcesRound134(RatedforDiv.2)目录EducationalCodeforcesRound134(RatedforDiv.2)D.MaximumANDE.PrefixFunctionQueriesD.Maximum......
  • Codeforces Round #606(B-D)
     Dashboard-CodeforcesRound#606(Div.2,basedonTechnocup2020EliminationRound4)-CodeforcesB.MakeThemOdd题意:一个数组,每次选择一个数,将数组中的......
  • Codeforces Round #817 (Div. 4) ABCDEFG
    https://codeforces.com/contest/1722/problem/A#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;typedefpair<int,int>PII;constintN=200200,......
  • Codeforces Round #817 (Div. 4)
    CF传送门因为洛谷题库未更新,所以给出的题面都是CF的。现场打真是太卡了(梯子挂了,codeforc.es也崩了),所以五六分钟才打开题目\(qwq\)A.SpellCheck萌萌题,把字符串放桶里......
  • Codeforces Round #817 (Div. 4)E Counting Rectangles
    CountingRectangles思维把所有的矩形左上角都叠在一起,就会发现是一个二维前缀和的求解问题:\(\sum_{i=h_s+1}^{h_b-1}\sum_{j=w_s+1}^{w_b-1}(i*j*cnt_{ij})\)这个显......
  • Codeforces Round #774 E
    这道题感觉没有E平时的难度首先我们感性理解一下相交的数只有可能是一个数的幂次才能相交比如248;3927;然后我们把他们行单独提出来再观察一下幂次发现其实都是......
  • Educational Codeforces Round 133 (Rated for Div. 2) ABD
    A.2-3Moves题意:从0,每次+2-2+3-3选一个,问多少次能到n由于对称性,先让n=abs(n)0只用0次,1只用1次t=n/3;如果n%3==1,说明t-1次+3,再来一次+2,就......