题目描述

起床困难症
https://www.acwing.com/problem/content/description/1000/

样例

import java.util.*;

public class Main {

    static final int N = 100010;
    static String[] ops = new String[N];
    static int[] val = new int[N];
    static int n, m, ans, x;//x:当前大小，ans:最终答案

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt(); m = sc.nextInt();

        for (int i = 0; i < n; i++) {
            ops[i] = sc.next();
            val[i] = sc.nextInt();
        }

        for (int i = 29; i >= 0; i--) {/*10^9需要30位比特位，而查看第一位需要右移0位，
        因此从29开始错开一位*/
            int ans0 = cal(i, 0), ans1 = cal(i, 1);//计算在第i为放0，和放1的比特位

            /*(x + (1 << i)) <= m: 在第i位放1要满足小于m(判断合法性) 并且ans1需要大于ans0(如果两边都是1, 
            不进行x的增加, 因为在在一次x的增值操作已经完成了对该位的增加,直接进入else即可)*/
            if ((x + (1 << i)) <= m && ans0 < ans1) {
                x += 1 << i;
                ans += ans1 << i;
            } else ans += ans0 << i; 
        }

        System.out.println(ans);
    }

    //计算该bit位放入u后进行操作后的比特位
    static int cal(int bit, int u) {
        for (int i = 0; i < n; i++) {
            int bitv = val[i] >> bit & 1;
            if (ops[i].equals("AND")) u &= bitv;
            else if (ops[i].equals("OR")) u |= bitv;
            else u ^= bitv;
        }

        return u;
    }
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla