题解 P2114 [NOI2014]起床困难综合症。

题意简述

给定 $n$ 个操作 $(op_i,t_i)$ ，其中 $op_i \in \{and,or,xor\}$ ，即三种位运算之一； $t_i$ 为非负整数。例： $a$ 一次操作后变为 $a$ $op_i$ $t_i$ 。

设 $f(x)$ 表示 $x$ 依次执行 $n$ 个操作后的结果。求： $\max\{f(x)\mid x\in [0,m]\}$ 。

思路

位运算具有一定的性质，二进制位之间不相互影响。假设一个数的二进制的第 $x$ 位是 $1$ ，经过一系列位运算之后得到的数的二进制第 $x$ 位是 $0$ ，那么只要一个二进制第 $x$ 位是 $1$ 的数，经过相同顺序的位运算，其得到的数的二进制的第 $x$ 位也一定是 $0$ 。

由于二进制的每一位只有 $0$ 和 $1$ 两种可能性，我们可以预处理出每一位置都是 $0$ 或者都是 $1$ 所得到的结果（即 $f(0)$ 与 $f(2147483647)$ ），预处理之后使用下面的贪心思路：

能用 $0$ 换 $1$ 就一定换；能用 $1$ 换 $1$ 也换，换后若初始攻击力大于 $m$ ，别换就好了。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int MAXN=100000+5;
	const int _and=1,_or=2,_xor=3;
	struct Doors{int opt,num;}door[MAXN];
	int n,m,bit0=0,bit1=2147483647,ans=0;
	int calc(int ans,int opt,int num)
	{
		if(opt==_and) ans&=num;
		else if(opt==_or) ans|=num;
		else ans^=num;
		return ans;
	}
	void yzmain()
	{
		string tmp;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		{
			cin>>tmp>>door[i].num;
			if(tmp=="AND") door[i].opt=_and;
			else if(tmp=="OR")  door[i].opt=_or;
			else door[i].opt=_xor;
		}
		for(int i=1;i<=n;i++)
		{
			bit0=calc(bit0,door[i].opt,door[i].num);
			bit1=calc(bit1,door[i].opt,door[i].num);
		}
		for(int i=31;i>=0;i--)//枚举每位，倒序枚举
		{
			if(bit0&(1<<i)) ans+=(1<<i); //能用0换1就一定换；
			else if((bit1&(1<<i))/*能用1换1也换*/&&(m>=(1<<i))/*但要保证初始攻击力不大于 m*/) ans+=(1<<i),m-=(1<<i);
		}
		printf("%d\n",ans);
		return;
	}
}
int main()
{
	//freopen("P2114_2.in","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}