P2114 [NOI2014] 起床困难综合症
分析
这题是关于二进制的题目,题目中描述了大量位运算的知识,其实也是在暗示这题与位运算有关了。
思考题目,题目要求我们在给定的值的范围内,进行一定数量的位运算,找到使最后运算得到的值最大的初始值。
既然要运算值最大,那么就要思考在二进制中怎样才能得到尽可能大的值。
二进制运算有一个特点,各个bit位上的值互不干扰,那么我们只要寻找每个bit位的最大值,即经过位运算是否有可能为1,最后将这个尽可能大的二进制数输出即可。
那么如何找到每个位置上尽可能大的值呢,我在洛谷的题解区看到大佬小粉兔的题解,也是让我眼前一新。
既然是要找到每个位置上的最大值,而每个位置又只有2种情况,即0和1,那么我们可以初始化a=0,b=-1,这样就会存在两个二进制数,一个都是0,一个都是1,
然后以a,b为基础进行位运算,设运算结束后为a1,b1,那么我们只要遍历bit位的位数,查看相应bit位上是否能取到1即可。
如果a1该位为1,则结果加上,该位为1,其他位为0所表示的二进制数。
否则的话,检查b1的这一位,,如果为1并且该二进制数不超过题目给出的初始值的范围(a为0,位运算后一定不会超过,所以不用检查),则加上,否则continue。
最后输出结果即可。
因为大佬的代码风格非常不错,还很简洁,我很是喜欢,所以就模仿了其风格,自己码了一遍
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
int a = 0, b = -1;
int main() {
int n, m;
cin >> n >> m;
string s;
int t = 0;
for (int i = 1; i <= n; i++) {
cin >> s >> t;
if (s[0] == 'A')
a &= t, b &= t;
if (s[0] == 'O')
a |= t, b |= t;
if (s[0] == 'X')
a ^= t, b ^= t;
}
int sum = 0;
for (int i = 30; ~i; i--) {//刚刚才看明白 ~i等价于i>=0,因为i=-1时候,~i=0
if (a >> i & 1) { // >>优先级高于&
sum += 1 << i;
} else if (b >> i & 1 && (1 << i) <= m) {
sum += 1 << i;
m -= 1 << i; //下次能从二进制数获取的值的上限减少
}
}
cout << sum << '\n';
return 0;
}
标签:总结,题目,运算,int,题解,好题,二进制,刷到,bit
From: https://www.cnblogs.com/STArunning/p/18052972