题目描述

一言蔽之：
你可以从0~m中选择一个数，让他和n个数进行给定的位运算，使最终答案最大。

样例

3 10
AND 5
OR 6
XOR 7

1

算法1

(位运算+贪心+枚举) $O(n*log(m))$

我觉得是一道在cf的div2中经常出现的一种题

基本就是贪心，从高位到低位考虑，高位尽可能让其为1

然后这里要分类讨论，要考虑的主要情况有下面几种：

1.and 0
2.or 1
3.xor 1

把这几种考虑到，基本就可以了，然后再对m的大小进行分析即可

其中有个转化的过程，把十进制转成二进制，写得挺乱的，供参考

时间复杂度

参考文献

C++ 代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f;
const int N=30;
int n,m,t[maxn],a[N];
string op[maxn];

/*
 a[i] = 1 bit变1
      = 0    变0
      = -1   不变
      = 2    翻转
*/

void solve() {
    memset(a,-1,sizeof(a));
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=N;j++,t[i]>>=1)
        if(op[i]=="AND"&&(t[i]&1)==0) {
            a[j]=0;
        } else if(op[i]=="OR"&&(t[i]&1)==1) {
            a[j]=1;
        } else if(op[i]=="XOR"&&(t[i]&1)==1) {
            if(a[j]==-1) {
                a[j]=2;
            } else if(a[j]==2) {
                a[j]=-1;
            } else {
                a[j]=!a[j];
            }
        }
    }
    bool flag=0;
    ll ans=0;
    for(int i=N;i>=1;i--) {

        if(a[i]==1) {
            ans+=(1<<(i-1));
            if(m&(1<<(i-1))) flag=1;
        } else if(a[i]==2) {

            ans+=(1<<(i-1));
            if(m&(1<<(i-1))) flag=1;

        } else if(a[i]==-1) {
            if(m&(1<<(i-1))) ans+=m&(1<<(i-1));
            else if(flag) ans+=(1<<(i-1));

        } else if(a[i]==0){
            if(m&(1<<(i-1))) flag=1;
        }
    }
    cout<<ans<<endl;
}


int main()
{
//  freopen("d:\\in.txt","r",stdin);
    //cout<<log(1000000000) / log(2)<< endl;

    cin>>n>>m;

    for(int i=1;i<=n;i++) {
        cin>>op[i]>>t[i];
    }
    solve();
    return 0;
}