Meeting-in-the-Middle，又称“中途相遇法”。准确地说，它只是一种策略。
顺便说一下，这个算法真的很冷门！
结合这道题来讨论一下吧：LA 2965。ε(┬┬﹏┬┬)3
因为博主的英文实在是十分拙劣，所以只能给出题目大意：
题目大概是说，输入多组数据(组数未知 反正不多啦)，每组给定一个$k<=24$，代表有k个字符串。
然后每组的后k行，依次输入这么多个字符串。
要求你选择尽量多的字符串，使得被选的字符串中的所有字母中，每种字母都出现偶数次。
输出选择字符串数，并从小到大输出被选字符串。
给组样例吧：
in
1 ABC 6 ABD EG GE ABE AC BCD
out
0 5 1 2 3 5 6
这个题目，乍一看上去，博主就只想到了模拟。。。（博主蒟蒻一枚）。
事实上，仔细分析，我们会发现：
这个题目，和字母的个数实际上没多大关系，更多的是和字母出现次数的奇偶有关。
于是我们假设有这么一张表：（拿样例中k=6的那一组为例）
A B C D E F G H…… 1 1 0 1 0 0 0 0 …… 0 0 0 0 1 0 1 0 …… 0 0 0 0 1 0 1 0 …… 1 1 0 0 1 0 0 0 …… 1 0 1 0 0 0 0 0 …… 0 1 1 1 0 0 0 0 ……
代表什么呢？显然这个表上的每一行都是一个26为的二进制数，而每一位对应一个字母，代表这个字母在此串中出现次数的奇或偶。
1代表的是奇，0代表的是偶。
仔细想想，我们是不是只要这么做：选择尽量多的串，使其异或值为0。
好。有了这张表，这就好办了。我们可以进行暴力穷举法$O（2^n）$。是不是还是很low？显然，这个时间复杂度过不了规模高达24的数据。
那么，我们怎么办呢？
这时候，我们开始讲到的MITM策略就可以派上用场了。
别看它的名字这么高级，其实思想主要是：
将待测数据（也就是那张表）分成两部分，枚举上表的所有子集的xor值，放入一个hash表或者map映射里。
然后枚举后半部分的数据所能得到的所有xor值，并每次都在hash表或者map映射里查找。
如果用map实现的话，总时间复杂度为$O（2^{（n/2）}logn）$，即$O（1.414^nlogn）$，比第一种方法好了很多。
这就是Meeting-in-the-Middle中途相遇法。
据刘汝佳神犇所述：密码学中的著名的中途相遇攻击（Meeting-in-the-Middle attack）就是基于这个原理。
最后贴上代码吧：
#include <bits/stdc++.h> using namespace std; const int maxn=24; map <int,int> table; int bitcount(int x) { return x==0?0:bitcount(x/2)+(x&1); }//这个函数用来计算这个数在二进制下有多少个1 int main() { int n,A[maxn]; char s[1000]; while (scanf("%d",&n)==1&&n) {//读入多组数据 for (int i=0;i<n;i++) { scanf("%s",s);//输入字符串 A[i]=0; for (int j=0;s[j]!=' ';j++) A[i]^=(1<<(s[j]-'A'));//计算每一串的<=26位二进制值 } table.clear();//清空table映射 int n1=n/2,n2=n-n1;//将待测数据分成两部分 //接下来循环计算2^(n/2)个属于前半部分的子集 for (int i=0;i<(1<<n1);i++) { int x=0; for (int j=0;j<n1;j++) if (i&(1<<j)) x^=A[j]; if (!table.count(x)||bitcount(table[x])<bitcount(i)) table[x]=i; }//取每个计算结果中的最大值 //最后处理后半部分 int ans=0; for (int i=0;i<(1<<n2);i++) { int x=0; for (int j=0;j<n2;j++) if (i&(1<<j)) x^=A[n1+j]; if (table.count(x)&&bitcount(ans)<bitcount(table[x])+bitcount(i)) ans=(i<<n1)^table[x]; }//每次计算前查找映射中是否出现过 printf("%d ",bitcount(ans)); for (int i=0;i<n;i++) if (ans&(1<<i)) printf("%d ",i+1); printf(" ");//输出部分 } return 0; }
如果不用map也可以改成哈希(hash)：
int insHash(int x) { int c=x%MOD; for (int u=h[c];u;u=nexp[u]) if (val[u]==x) return u; if (!gans) nexp[p]=h[c],h[c]=p,val[p]=x,p++; return -(p-1); }
然后听机房一位神犇说，这题用深搜(dfs)枚举子集会更快，虽然不知为何？
void dfs(int f,int sum,int k) { if (f>upb){ if (sum==-1) return; x=insHash(sum); if (!gans) { if (x<0) x=-x; if (k>cnt[x]) cnt[x]=k; } else if (x>0&&cnt[x]+k>ans) ans=cnt[x]+k; else if (!sum&&k>ans) ans=k; return; } dfs(f+1,sum==-1?num[f]:sum^num[f],k+1); dfs(f+1,sum,k); }