美团8.19第三题-01权值

我看到大家好像都是用动态规划, 没有用位操作的. s 只可能翻转成两种序列:

• 101010
• 010101

并且注意到, s 与这两种序列做异或, 得到 1 的个数就是转为对应序列的操作数, 两个中取最小值则是权值. 即:

• 10001 ^ 10101 = 00100
• 10001 ^ 01010 = 11011

使用 BitSet将 s 与这两种序列做异或, 对应区间 1 的个数就为对应区间的权值. 也可以使用前缀和, 这样查询就是 `O(1)`

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String s = in.nextLine();

            int n = s.length();
            long res = 0;

            BitSet b = new BitSet(n); // 原始序列
            BitSet b1 = new BitSet(n); // 101010序列
            BitSet b2 = new BitSet(n);// 010101序列
            for (int i = 0; i < n; i++) {
                int num = s.charAt(i) - '0';
                if (num == 1) {
                    b.set(i);
                }

                int n1 = i % 2;
                if (n1 == 1) {
                    b1.set(i);
                }

                int n2 = (i + 1) % 2;
                if (n2 == 1) {
                    b2.set(i);
                }
            }
            // 异或
            b1.xor(b);
            b2.xor(b);

            for (int i = 0; i <= n - 2; i++) {
                for (int j = i+1; j < n; j++) {
                    // 查询对应区间的 1, 也可使用前缀和
                    int i1 = b1.get(i, j+1).cardinality();
                    int i2 = b2.get(i, j+1).cardinality();

                    res += Math.min(i1, i2);
                }
            }

            System.out.println(res);
        }
    }