折半搜索（中途相遇法） + 暴力枚举：PIPI的炼金术

小咪咪 2023-10-06 22:04 6阅读 0赞

## 折半搜索（中途相遇法） + 暴力枚举：PIPI的炼金术 ##

#### 文章目录 ####

*  折半搜索（中途相遇法） + 暴力枚举：PIPI的炼金术
 *   *   *  问题：
         *  思路：
         *  代码：

#### 问题： ####

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 思路： ####

首先我们要把问题进行一个转化。根据题意，我们把若干材料炼金成功，只需这些材料字符串各个字符出现个数之和为偶数就行，而材料字符串全都是由小写字母组成，小写字母a-z可以对应数字0-25。因此我们可以考虑如下操作：我们将每个字符串中字符的出现次数是偶数还是奇数记录下来，用二维数组alphabet保存，`alphabet[i][j]=0`表示第i个字符串的字母j出现次数为偶数，`alphabet[i][j]=1`表示第i个字符串的字母j出现次数为奇数。然后我们可以将每个材料字符串26个字母的出现个数是偶数还是奇数的信息转化为一个26位的二进制数字，若某位为1，表示该位置对应字母的出现个数为奇数，反之为偶数。那么n个字符串也就变成了n个数字，所以问题就变成了：对于n个数字，你可以从中任取若干个(但数量必须大于0)数字，把他们全部异或起来，其值若为0，即是一种合法的方案（因为若要组合之后的字符串字母出现次数为偶数，则被组合的原始字符串中该字母出现次数要么都为奇数，要么都为偶数，这正好对应了相应2进制位中1 1和0 0的情况，而相同的异或为0，正好对应组合后字母出现次数为偶数，然后若异或结果为值0，则是所有二进制位都为0，对应所有字符出现次数为偶数，即题中的条件）。  
  进行完转化后，就到了统计方案个数的问题。题中可以组合任意字符串，对于每个字符串，显然，都有选或不选两种选择，因此很容易想到O(2^n)的暴力枚举法，从000…001枚举到111…111，然后通过位运算和移位将对应选中的字符串异或起来。但是本题n的大小有35，时间复杂度过不去。这时候我们就需要用折半搜索法优化时间复杂度。  
  折半搜索也叫中途相遇法。简单来说就是处理前一半，把结果储存起来，再处理后一半，然后匹配前一半存储的结果。也就是在枚举后一半时利用前一半产生的结果，避免重复计算。  
  对于此题，就是先枚举一半，从1（对应000…001）枚举到`2 ^ (n / 2 + 1) - 1`（对应000…111…111），若异或结果为0，则结果ans++，表示找到一种方案，无论异或结果如何，都把计算出该异或结果的个数用哈希表保存。然后我们枚举另一半，从`2 ^ (n / 2 + 1)`（对应000…100…000）枚举到后半段全1（即对应111…111000…000），注意我们枚举后半段时步长为`2 ^ (n/2 + 1)`，即我们枚举后半段，表示枚举后半段的字符串，这时我们完全不考虑前半段的字符串，即枚举时前半部分的二进制位都为0。若异或结果为0，则结果ans++，表示找到一种方案，无论异或结果如何，都去查询哈希表，若哈希表中保存了当前计算出的异或值，则表示前半段枚举中出现了和当前字符奇偶分布情况一模一样的，那么我们需要用ans加上哈希表中存储的方案数，因为之前保存的方案可以组合当前方案，从而到达题目要求。（因为若两个组合字符串字符奇偶分布一模一样，那么它们再进行组合，所有字符肯定都出现偶数次）。  
  这样，通过折半搜索，时间复杂度就从O(2 ^ n)优化成O(2 ^ (n/2))了。

#### 代码： ####

import java.util.*;
    
    public class Main {
        
        static int[][] alphabet = new int[37][27];
        static long[] hash = new long[37];
        static long[] twoMul = new long[37];
        static HashMap<Long, Long> num = new HashMap<>();
        public static void main(String[] args) {
        
            int n, i, j, count;
            long loop, temp, k, ans = 0, hVal;
            twoMul[0] = 1;
            for (i = 1; i < 37; i++) {
        
                twoMul[i] = twoMul[i - 1] * 2;
            }
            StringBuilder stringBuilder = new StringBuilder();
            Scanner scanner = new Scanner(System.in);
            n = scanner.nextInt();
            for (i = 0; i < n; i++) {
        
                stringBuilder.delete(0, stringBuilder.length());
                stringBuilder.append(scanner.next());
                for (j = 0; j < stringBuilder.length(); j++) {
        
                    if (alphabet[i][stringBuilder.charAt(j)-'a'] == 1) {
        
                        alphabet[i][stringBuilder.charAt(j)-'a'] = 0;
                    } else {
        
                        alphabet[i][stringBuilder.charAt(j)-'a'] = 1;
                    }
                }
            }
            for (i = 0; i < n; i++) {
        
                for (j = 0; j < 26; j++) {
        
                    hash[i] += alphabet[i][j] * twoMul[j];
                }
            }
            for (loop = 1; loop <= twoMul[n / 2 + 1] - 1; loop++) {
        
                temp = loop;
                count = 0;
                k = 0;
                while (temp != 0) {
        
                    if ((temp & 1) != 0) {
        
                        k = hash[count] ^ k;
                    }
                    temp >>= 1;
                    count++;
                }
                if (k == 0 && count != 0) {
        
                    ans++;
                }
                if (num.get(k) != null) {
        
                    hVal = num.get(k);
                    num.put(k, hVal + 1);
                } else {
        
                    num.put(k, 1L);
                }
            }
            for (; loop <= twoMul[n] - 1; loop += twoMul[n / 2 + 1]) {
        
                temp = loop;
                count = n / 2 + 1;
                k = 0;
                while (temp >= twoMul[n / 2 + 1]) {
        
                    if ((temp & twoMul[n / 2 + 1]) != 0) {
        
                        k = hash[count] ^ k;
                    }
                    temp >>= 1;
                    count++;
                }
                if (k == 0 && count != n / 2 + 1) {
        
                    ans++;
                }
                if (num.get(k) != null) {
        
                    hVal = num.get(k);
                    ans += hVal;
                }
            }
            System.out.println(ans);
        }
    
    
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/71d4e4c654c546fbb0c7209c53580932.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/4f1fa644d4cc4b0a823ec4b790a3cd67.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16