6676. 度度熊与运算式 1

2020-04-03

HDOJ

2019 年百度之星·程序设计大赛 - 初赛二

7 分钟读完 (大约 986 个字) 0次访问

HDOJ 6676. 度度熊与运算式 1

2019 年百度之星·程序设计大赛 - 初赛二

6674. 度度熊与数字

6675. 度度熊与排列

6676. 度度熊与运算式 1

题目：6676. 度度熊与运算式 1

问题描述：

某天度熊发现了一个由 n+1 个数字 1 组成的运算式如下：

1 op1 1 op2 1 … 1 opn 1

其中 opi 可能是 ⊕ (按位异或运算) 或是 ? (问号)。

例如当 n=5 时，式子可能长成这样：1⊕1 ? 1⊕1 ? 1 ? 1

现在，度熊想把所有的 ‘?’ 取代为 + 或 ⊕。

(贴心提示：加法运算的优先级比按位异或运算还高)

请问取代完后此运算式可能的最大运算结果为何？

输入：

有多组询问，第一行包含一个正整数 T 代表有几组询问，接着每组测试数据占一行，包含一个长度为 n 的字符串，仅由 ‘^’和 ‘?’组成，第 i 个字符若是 ‘^’ 就代表 opi=⊕，否则 opi 就是问号。(n 的值不会在数据中出现，请由字符串长度来判断。)
1≤n≤2^21−2
所有询问的 n 的总和不超过 2×10^7

输出：

对于每一个询问输出一行包含一个整数代表答案，也就是该算式的问号被取代后可能的最大运算结果。

样本输入：

4
?
??
^^
^^^

样本输出：

2
3
1
0

注意：

样例的第一组询问算式为：1?1。取代后有 2种可能 1+1和 1^1，其中 1+1=2、1^1=0，所以最大的可能值是 2。

样例的第二组询问算式为：1?1?1。取代后有 4 种可能 1+1+1,1+1^1,1^1+1和 1^1^1，

样例的第三组询问算式为：1^1^1。并不包含问号，只有唯一的运算结果 1。

样例的第四组询问算式为：1^1^1^1。并不包含问号，只有唯一的运算结果 0。

方法：异或原理

思路：将字符串按^分成多个小段，把每个小段整理成为2的i次幂（幂次i不能相同， i > 0）的段，从而使得不同幂次间的小段执行^时最大，再处理其他整理之后剩余的不满足2的i次幂（幂次i不能相同， i > 0）的段，这些剩余的小段要么不能分解为2的i次幂（小段的值是1），要么能分解但幂次与之前分解的小段相同(若分解，合并执行^时，会相互抵消，使得最后的值变小，所以这样的小段只能将小段中的？变为^，从而使得小段的值最小，执行^时相互抵消最小)

运行数据：执行用时：1014MS，内存消耗：15832K

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();

        while (t-- > 0) {
            String s = sc.next();

            // 记录1的个数
            int numLen = s.length() + 1;

            // 用split方法分段
            String[] sections = s.split("\\^");

            // 分段数
            int sectionLen = sections.length;

            // 如果分段数为0，说明源字符串s全为^
            if (sectionLen == 0) {
                System.out.println(numLen % 2);
                continue;
            }

            // 将每一段整理分成多个2的i次幂（幂次i不能相同， i > 0）段并执行^，余下不为2的i次幂（幂次i不能相同， i > 0）的段不处理
            int sum = 0;
            for (String section : sections) {
                int len = section.length() + 1;
                for (int i = Integer.toBinaryString(len).length() - 1; i >= 1; i--) {
                    if ((sum & (1 << i)) > 0 || len < (1 << i)) continue;
                    len -= (1 << i);
                    sum ^= (1 << i);
                }
            }

            // 判断余下不为2的i次幂（幂次i不能相同， i > 0）的段的和是否为奇数
            if ((numLen - sum) % 2 > 0) sum ^= 1;

            System.out.println(sum);
        }
    }
}