起床困难综合症

起床困难综合症

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

分析

由于混合位运算并不具备结合律,所以我们应该是不能强制将式子化简的。但是我们考虑位运算的本质。举一个例子 运算,我们如果完整的写出表达式为 我们可以发现,其实位运算的结果只取决于每一位,而并不是整个数字的值。那么我们可以按位考虑每一位,其实按位考虑也是解决关于位运算问题的一种常见方法。我们可以令 表示一个数第 位是 最后经过一系列位运算后变为的答案。那么我们考虑最后的答案就可以贪心考虑了。我们按大到小枚举每一位。

  • 这时候我们显然应该让答案 ,因为我们对于 是有大小限制的,如果第 都不影响答案,我们显然使 这样才有可能满足更多的条件。

  • 这时候我们需要判断一下 。如果可以满足 我们是一定要选取的,因为即使后面的条件全部满足,所能贡献的答案也只有 ,这显然是没有 大的。

  • 其他情况,肯定是 优先。因为这个不会影响后面的选择。

那么最后的复杂度为

  • 在做有关位运算的题,我们尽量考虑使用 类型的数。因为可能会避免一些关于值域的坑,也避免了负数的产生。

代码

#include<bits/stdc++.h>
using namespace std;
unsigned int n,m,S1,S0;
int main() {
    S1 = -1;S0 = 0;scanf("%u%u",&n,&m);
    for(int i = 1,x;i <= n;i++) {
        static char ch[10];
        scanf("%s%u",ch + 1,&x);
        if(ch[1] == 'A') S1 &= x,S0 &= x;
        if(ch[1] == 'O') S1 |= x,S0 |= x;
        if(ch[1] == 'X') S1 ^= x,S0 ^= x;
    }
    int ans = 0;
    for(int j = 31,x = 0,flag = 0;~j;j--) {
        if((S0 >> j) & 1) ans += (1 << j);
        else if(((S1 >> j) & 1) && ((x + (1 << j)) <= m)) x += (1 << j),ans += (1 << j);
    }
    cout << ans << endl;
}
数学 文章被收录于专栏

关于多项式

全部评论
感谢老哥,通俗易懂
点赞 回复 分享
发布于 02-17 17:16 湖北
为啥第一个要是-1捏
点赞 回复 分享
发布于 2023-10-19 17:31 江苏
tql
点赞 回复 分享
发布于 2020-10-21 20:59

相关推荐

07-04 21:23
已编辑
东莞城市学院 后端
秋招和春招只收到几个中大厂的笔试,本人比较菜,感觉大厂的笔试太难,算法题不能全部做出来就没过了,但是CVTE和小天才的感觉不是很难,基本上都做出来了,笔试还是挂了。Boss上投了Java后端开发都没有回音,boss上有面试机会都是C#工控软件开发方向的,但是这个方向不太懂,资料又少,面试的表现有点差,现在还是想看看Java这边,面试的时候比较有把握点。想请教一下,这份简历还有什么问题,一直没什么机会,还有什么地方要修改的。
程序员小白条:学历太差,民办和公办,外包还得区分的,这个学历+这个简历,没的办法,除非你有人脉,太难了,这环境,何况你都毕业了,连一段实习都没,肯定没公司会挑选了,没竞争力,开发才招几个人,跟你竞争的可不是二本,三本的人哦,何况你在二本,三本里面也排名不高
投递小天才等公司7个岗位
点赞 评论 收藏
分享
深夜书店vv:腾讯是这样的,去年很多走廊都加桌子当工区
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 17:10
点赞 评论 收藏
分享
评论
13
4
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务