起床困难综合症

题目链接

这么好的一道二进制题怎么能不写呢?

解题思路

既然题目中这么明显地有二进制了,肯定要想到将每个数拆成二进制形式看。

答案的某一位的大小取决于初始攻击那一位的大小,与更高位和更低位没有任何关系。

由于答案要最大,那么就是说答案的最高位大小优先最大。

所以我们将初始攻击(二进制)从高位开始尝试,只有0和1两种可能,每种可能都将所有操作在对应位数上做完即可,即 op (t<<位数)&1

于是我们得到了两个答案。但是由于有m限制我们的最大大小,需要用一个val记录当前的数的大小。

最后最重要的判断语句:

if(这一位取1时>这一位取0时&&这一位取1不会超出初始攻击的范围m){
更新当前数的大小;
最终答案+=这一位取1的结果;
}else{
最终答案+=这一位取0的结果;
}

代码

#include<bits/stdc++.h>
using namespace std;
string str[100005];
int a[100005];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>str[i]>>a[i];
    }
    int ans=0;
    int val=0;
        //将位数从高到低一个一个判断
    for(int i=29;i>=0;i--){//不要取太大的数,因为如果a[j]>>i超出范围就惨了。。。我就是这样调了半小时的。。。
        int tmp=0;
                //将每个操作都过一遍
        for(int j=0;j<n;j++){
            int zhi=(a[j]>>i)&1;//将a对应位的值拿出来
                //以下为各种操作
                        if(str[j]=="AND"){
                tmp&=zhi;
            }else if(str[j]=="OR"){
                tmp|=zhi;
            }else{
                tmp^=zhi;
            }
        }
                //这里和上面唯一的不同是设了tm为1,当然大家也可以写个函数。
        int tm=1;
        for(int j=0;j<n;j++){
            int zhi=(a[j]>>i)&1;
            if(str[j]=="AND"){
                tm&=zhi;
            }else if(str[j]=="OR"){
                tm|=zhi;
            }else{
                tm^=zhi;
            }
        }
        if(val+(1<<i)<=m&&tm>tmp){
            ans+=tm<<i;
            val+=1<<i;
        }else{
            ans+=tmp<<i;
        }
    }
    cout<<ans;
    return 0;
} 

本文链接:https://kaispace.com.cn/index.php/archives/521/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者