题解 洛谷P2114 起床困难综合征

发布于 2019-06-08  46 次阅读


首先这是一道有关位运算的题

位运算的主要特点之一就是在二进制表示下不进位,参与位运算的各个位之间是独立无关的。

那么从每一位来看位运算的结果,无论中间的操作如何,最终的这一位的结果都只有两种情况:0或1。

那么中间的一系列的OP_i 对于每一位而言都可以合并为同一个式子。

每一位的运算结果可以分为四种情况:

  • 0→1 1→1

  • 0→1 1→0

  • 0→0 1→1

  • 0→0 1→0

这样一来事情就好办了

我们由数据范围可以知道总的二进制位数不超过30位,我们令a1在二进制下全为0,即a1=0,令a2在二进制下全为1,即a2=0x7fffffff,将a1与a2进行通过防御门即可得知最终的运算结果。

对于初始攻击力的范围m,我们只需要贪心,从高位到低位能1则1,大于m则0即可,因为位运算结果位只和原先的那一位有关啦~

代码如下

#include<iostream>
#include<cstdio>
using namespace std;
string op;
int i,n,m,ans=0,t,a1=0,a2=0x7fffffff;
int main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		cin>>op>>t;
		if (op[0]=='A') a1&=t,a2&=t;
		if (op[0]=='O') a1|=t,a2|=t;
		if (op[0]=='X') a1^=t,a2^=t; 
	}
	for (int i=29;i>=0;i--)
		if (((a1>>i)%2)==1) ans+=1<<i;//对应0变成1的情况
		else if ((a2>>i&1==1) && ((1<<i)<=m)) ans+=1<<i,m-=1<<i;//对应1变成1的情况
	//任意数变成0的情况不需要考虑,对m无影响
	// &1即为%2,但要注意运算优先级 
	cout<<ans<<endl; 
	return 0;
}

Cause this is the life. Living is do or die.