P2114 [NOI2014]起床困难综合症 （位运算）

题目意思:
算法竞赛进阶指南， 8 页
1、位运算， 不产生进位
2、依次遍历每一二进制位，看看填1还是0
3、第 k 位填1 的条件（从高位到低位）
1）已经填好的高位数值 val 加上 1 << k ， val + (1 << k) <= m
2）res0 == 0 && res1 == 1 //也就是 res0 < res1
4、 如果 不满足条件3
1）val + (1 << k) > m, 此时 k位填0
2）(res0 == 1 || res1 == 0)
a) res0 == 1 && res1 == 0
b) res0 == 1 && res1 == 1
c) res0 == 0 && res1 == 0
这三种情况，优先选择 k 位 是 0

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;const int MaxN = 100010;
char cmd_op[MaxN][5];
int cmd_num[MaxN];int n, m;int calc(int bit, int now)//用参数的第 bit 位进行n次运算
{
    								for(int i = 1; i <= n; ++i){
    int x = cmd_num[i] >> bit & 1;if(cmd_op[i][0] == 'A'){
    now &= x;	}else if(cmd_op[i][0] == 'O'){
    now |= x;}else{
    now ^= x;}}return now;
}int main()
{
    scanf("%d%d", &n, &m);for(int i = 1; i <= n; ++i){
    scanf("%s %d", cmd_op[i], &cmd_num[i]);}int val = 0, ans = 0;// val 作为中间值// 遍历 每一位的二进制位for(int bit = 30; bit >= 0; --bit){
    int res0 = calc(bit, 0);int res1 = calc(bit, 1);if(val + (1 << bit) <= m && res0 < res1)// res0 < res1 实际相当于 res0 == 0 && res1 == 1{
    val += 1 << bit;ans += res1 << bit;}else{
    ans += res0 << bit;}}printf("%d\n", ans);return 0;
}/* 3 10 AND 5 OR 6 XOR 7 *//* 1 */