浅析 NC17857 起床困难综合症

题目链接：https://ac.nowcoder.com/acm/problem/17857

题面：

21 世纪，许多人得了一种奇怪的病：起床困难综合症，其临床表现为：起床难，起床后精神不佳。作为一名青春阳光好少年，atm 一直坚持与起床困难综合症作斗争。通过研究相关文献，他找到了该病的发病原因：在深邃的太平洋海底中，出现了一条名为 drd 的巨龙，它掌握着睡眠之精髓，能随意延长大家的睡眠时间。正是由于 drd 的活动，起床困难综合症愈演愈烈，以惊人的速度在世界上传播。为了彻底消灭这种病，atm 决定前往海底，消灭这条恶龙。

历经千辛万苦，atm 终于来到了 drd 所在的地方，准备与其展开艰苦卓绝的战斗。drd 有着十分特殊的技能，他的防御战线能够使用一定的运算来改变他受到的伤害。具体说来，drd 的防御战线由 𝑛 扇防御门组成。每扇防御门包括一个运算 op 和一个参数 𝑡，其中运算一定是 OR,XOR,AND 中的一种，参数则一定为非负整数。如果还未通过防御门时攻击力为 𝑥 ，则其通过这扇防御门后攻击力将变为 𝑥 op 𝑡 。最终drd 受到的伤害为对方初始攻击力 𝑥 依次经过所有 𝒏 扇防御门后转变得到的攻击力。由于atm 水平有限，他的初始攻击力只能为 0 到 𝑚 之间的一个整数（即他的初始攻击力只能在 0, 1, … , 𝑚 中任选，但在通过防御门之后的攻击力不受 𝑚 的限制）。为了节省体力，他希望通过选择合适的初始攻击力使得他的攻击能让 drd受到最大的伤害，请你帮他计算一下，他的一次攻击最多能使 drd 受到多少伤害。

数据范围：

2 $\leqslant$ n $\leqslant$ 10⁵
2 $\leqslant$ m $\leqslant$ 10⁵
0 $\leqslant$ t $\leqslant$ 10⁹
每个门的 op 为 OR,XOR,AND 中的一种

思路

暴力是无法AC的，对于包含OR,XOR,AND的题，可以考虑转换为二进制来简化处理，因为二进制的每一位之间互不影响，相互独立，更方便按位独立处理

(就像贪心的时候只希望能考虑到局部，且局部的变动不会影响到其他部分（如：NC16561国王的游戏中：一维数组中相邻两个数的位置交换不会影响它们两个数的前面和后面的数的统计）)

从二进制按位处理的角度思考，判断每一位二进制位通过所有的门的位运算后的处理结果是 0 还是 1 ，可以分别用 0 和 1 做初始输入来尝试。

最后得到的变化结果分析：

如果原先是 0 ，经过全部位运算后变为 1 ，空手套白狼，不费力就增加伤害（很棒）（通常表现在二进制高位上）（该位初始设为 0 更好）

如果原先是 1 ，经过全部位运算后变为 0 ，费力不讨好，努力也没有伤害（摆烂）（该位初始设为0更好）

若该位初始设 0 设 1 都一样，为了节省体力，该位初始设为0更好

。。。。。。

注意最后结果要求得的是最终伤害值，不是初始攻击力！！！

代码：

#include<iostream>
#include<cstring>

using namespace std;

int n, m;

int main ()
{
	cin >> n >> m;
		
	string tmp;
	int t;
	
	// 按位独立尝试 0 和 1 分别经过所有门的位运算后的结果
	int one = (1 << 31) - 1;  // one = -1 也行
	int zero = 0;
	
	for (int i = 1; i <= n; i++)
	{
		cin >> tmp >> t;
		if (tmp == "AND")
		{
			one = (one & t);
			zero = (zero & t);
		}		
		else if (tmp == "OR")
		{
			one = (one | t);
			zero = (zero | t);
		}
		else 
		{
			one = (one ^ t);
			zero = (zero ^ t);	
		}
	}

	int ans = 0, beat = 0; // 造成的总伤害值 ans， 自身的初始攻击力 beat (beat <= m)
	for (int i = 32; i >= 0; i--)
	{
		// 初始为 0 ，经过所有门的位运算后变为 1，空手套白狼
		if ((zero>>(i-1)) & 1)   
		{
			ans += (1<<(i-1));
		}
		
		// 初始为 0 ，经过所有门的位运算后变为 0  ----  ！((zero>>(i-1)) & 1) 
		// 初始为 1 ，经过所有门的位运算后变为 1  ----  ((one>>(i-1)) & 1) 
		// 且所累加的攻击力 beat 没有超过上限 m   ----  beat + ((1<<(i-1)) <= m)
		else if (((one>>(i-1)) & 1) && beat + ((1<<(i-1)) <= m))
		{
			beat += (1<<(i-1));
			ans += (1<<(i-1));
		}
	}
	
	cout << ans;
}