起床困难综合症

起床困难综合症

https://ac.nowcoder.com/acm/problem/17857

题意:
选一个小于m的数,始得他经过一系列位运算后值最大。
题解:
因为数特别大,所以无法用暴力解决。
一开始想了贪心,不过只考虑了用111111111111这样的二进制过一遍然后检查得到的数,忘了可以用0过一遍了。
看了大佬的题解才恍然大悟,因为这题基础是位运算,所以我们我们把每一位拆开进行判断。
贪心这个想法是从,这个数要小于m得出的。
我们从最高位开始进行贪心,如果这个位一开始位0,经过这一些列位运算后,得出1,那么我们可以直接把答案的 这一位 变成0,因为贪心(尽可能让这个数不要超过m),如果经过这一些列位运算后,得出0,那么我们就需要康康 能不能 把答案的 这一位 变成1。因为答案要求这个数要小于m,如果这一位加上去之后,小于m,那么我们就可以把这一位 变为1,同时m减去这一位的大小。

代码:

/*Keep on going Never give up*/
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define Accepted 0
#define AK main()
#define I_can signed
using namespace std;
const int maxn =1e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
using namespace std;

int x,y;
I_can AK
{
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    y=-1;
    for(int i=0;i<n;i++){
        string s;
        int num;
        cin>>s>>num;
        if(s[0]=='A') x&= num,y&=num;
        else if(s[0]=='X') x^=num,y^=num;
        else x|=num,y|=num;
    }
    int ans=0;
    for(int i=1<<30;i;i>>=1){
        if(x&i) ans+=i;
        else if(y&i&&i<=m) ans+=i,m-=i;
        //cout<<11<<endl;
    }
    cout<<ans<<endl;
    return 0;
}
题解 文章被收录于专栏

主要写一些题目的题解

全部评论

相关推荐

2 1 评论
分享
牛客网
牛客企业服务