简介：
\(\mathbf{meet}\) \(\mathbf{in}\) \(\mathbf{the}\) \(\mathbf{middle}\) 是一种特殊的搜索技巧，利用了“折半”这种思想，先分别搜出两半子问题的答案，再利用总问题与子问题之间的关系进行合并，得出答案。
关于时间复杂度：
原问题的搜索往往是 \(\Theta(2^n)\) 复杂度，折半后复杂度同时折半，当然还要算上合并答案的复杂度（这类复杂度往往不会太高）。
练习：
世界冰球锦标赛
当然是 \(\mathbf{meet}\) \(\mathbf{in}\) \(\mathbf{the}\) \(\mathbf{middle}\) 的模板题，首先爆搜不用多说，考虑如何合并答案：我们将前后两半子问题的每种状态搜出来，再将前半段状态按照答案排序，利用 upper_bound 查出前驱进行统计。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=55,M=1<<21;
int n,m,w[N],mid,suma[M],sumb[M],cnta,cntb,ans;
void dfs(int l,int r,int sum,int a[],int &cnt){
if(sum>m) return;
if(l>r) return a[++cnt]=sum,void();
dfs(l+1,r,sum+w[l],a,cnt);
dfs(l+1,r,sum,a,cnt);
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
mid=n>>1;
dfs(1,mid,0,suma,cnta);
dfs(mid+1,n,0,sumb,cntb);
sort(suma+1,suma+1+cnta);
for(int i=1;i<=cntb;i++)
ans+=upper_bound(suma+1,suma+1+cnta,m-sumb[i])-suma-1;
cout<<ans;
return 0;
}
期末考试
知道了 \(\mathbf{meet}\) \(\mathbf{in}\) \(\mathbf{the}\) \(\mathbf{middle}\) 这题就比较容易了，首先爆搜是平凡的，枚举每个状态一个一个对号就行，但是超时。因此考虑如何合并答案：我们为前半子问题的每一个答案开桶计数，对后半子问题的每个答案查 \(m-sum\) 即可，当然这 \(n\) 次的回答是统一的，不能分开统计，因此我们计算对于 \(n\) 次回答每个最终的得分并将这 \(n\) 个数哈希起来，统一考虑即可。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e4+10,p=1e9+7;
int n,ans(0),hast1(0);
int d[N],b[N][15],a[N];
map<int,int> mp;
void dfs(int x){
if(x==6){
int has(0);
for(int i=1;i<=n;i++){
int op=0;
for(int j=1;j<=5;j++) if(d[j]==b[i][j]) op+=10;
if(op>a[i]) return;
has=(has*131%p+op)%p;
}
mp[has]++;
return;
}
d[x]=1;dfs(x+1);
d[x]=2;dfs(x+1);
d[x]=3;dfs(x+1);
d[x]=4;dfs(x+1);
}
void dfs1(int x){
if(x==11){
int has(0);
for(int i=1;i<=n;i++){
int op=0;
for(int j=6;j<=10;j++) if(d[j]==b[i][j]) op+=10;
if(op>a[i]) return;
has=(has*131%p+op)%p;
}
ans+=mp[(hast1-has+p)%p];
return;
}
d[x]=1;dfs1(x+1);
d[x]=2;dfs1(x+1);
d[x]=3;dfs1(x+1);
d[x]=4;dfs1(x+1);
}
char s[N][15];
signed main(){
// freopen("1.in","r",stdin);
ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
int T;cin>>T;
while(T-->0){
cin>>n;
hast1=0;
mp.clear();
for(int i=1;i<=n;++i){
for(int j=1;j<=10;++j) cin>>s[i][j];
for(int j=1;j<=10;++j){
if(s[i][j]=='A') b[i][j]=1;
if(s[i][j]=='B') b[i][j]=2;
if(s[i][j]=='C') b[i][j]=3;
if(s[i][j]=='D') b[i][j]=4;
}
cin>>a[i];
hast1=(hast1*131%p+a[i])%p;
}
ans=0;
dfs(1);dfs1(6);
cout<<ans<<endl;
}
}