CH-0104 起床困难综合症 题解

题目大意

让你在$[0,m]$中选一个数字，在经过n次位运算之后，（&，|，^），问求出的最大值为多少。

解题思路

这个题目是蓝书上的原题，最近开始补蓝书了。

如果可以的话，我会尽量把上面比较好，比较经典的题目都会重新写一遍。

这题是一道十分经典的位运算题。

首先，根据位运算的特性，即每一位的运算只与这一位有关，与其他位无关。

那么我们可以用每一位上的1和0来进行比较，判断该位上选0还是1更优。

如果初始为0的运算后能得到1，那么肯定选0。

如果初始为1的运算后能得到1，且得到的值t不会超过m，那么就可以选1。

其余情况都选择0。

遍历的话需要从高位到低位（但是跑出来的话从低到高也是对的，不知道是不是数据太水了。。

假如0的话每一位都是0，假如1的话每一位都是1。

m为1000 0000。

如果逆序的话，你可以得到1000 0000。

如果正序的话，你可以得到0111 1111。

很显然，逆序的值会大一些，所以需要逆序。

完整代码

#include <iostream>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	string s;
	int k;
	int ans0 = 0, ans1 = 0x7FFFFFFF;
	for (int i = 1; i <= n; i++) {
		cin >> s >> k;
		if (s == "AND")	ans0 &= k, ans1 &= k;
		else if(s=="OR")	ans0 |= k, ans1 |= k;
		else ans0 ^= k, ans1 ^= k;
	}
	int ans = 0;
	for (int i = 31; i >= 1; i--) {//逆序的贡献大一些，所以需要逆序
		int t = 1 << (i-1);
		if ((ans0>>(i-1)) & 1)	ans += t;
		else if ((ans1 >> (i - 1)) & 1 && m >= t)ans += t, m -= t;
	}
	cout << ans << endl;
}