起床困难综合症[二进制运算]

题面

[https://www.luogu.com.cn/problem/P2114]

分析

题目要求是从[0,m]中选出一个数，经过给定的n次运算，得到结果ans最大
位运算主要特点之一是二进制表示下不进位
所以对于一个确定的x经过n次运算之后每一位的值是固定的
即每位上1或0最后的结果是可以确定的
那么预处理每一位0或1最后运算的结果之后
为了使ans最大，能变1都变1（但是要保证原来的数<=m）

code（换马蜂了）

#include <iostream>
#include <cstdio>
using namespace std;
inline int read(){
	register int x = 0, f = 1;
	register char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = (x << 3) + ( x << 1) + c - '0',c = getchar();
	return x * f;
}
int n, m;
int a0 = 0,a1 = -1;//-1在计算机中以补码形式存在，-1的补码为1111111……1
int init(){
	n = read(), m = read();
	while (n--){
		char str[5];
		scanf ("%s", str);
		int t = read();
		if (str[0] == 'A') a0 &= t, a1 &= t;
		if (str[0] == 'X') a0 ^= t, a1 ^= t;
		if (str[0] == 'O') a0 |= t, a1 |= t; 
	}
}

int doit(){
	int val=0,ans=0;
	for (int i = 29; i >= 0;i--){
		if (a0 >> i & 1) ans += 1 << i;//0能变1直接变
		else if (a1 >> i & 1 && (1 << i) + val <= m) ans += 1 <<i, val += (1 << i);//1能变1也直接变，同时考虑初始值的大小要小于m
	}
	printf ("%d", ans);
}

int main(){
	init();
	doit();
	return 0;
}