【學(xué)習(xí)筆記】meet in middle
一、簡介
折半搜索，即對于那些數(shù)據(jù)范圍較小卻又不能直接暴搜的題目，采取分兩半暴搜后再想辦法合并兩部分的答案的辦法。一般的方式是二分或者狀壓、map。
二、例題
1.世界冰球錦標(biāo)賽
對前一半和后一半分別進(jìn)行暴搜，將前半部分的答案存起來并排序，對于每個(gè)后面的答案在這個(gè)序列中二分即可。時(shí)間復(fù)雜度 \(O(2^{\frac{n}{2}}n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define uprb upper_bound
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=(1<<20)+5;
int n,tot;
ll m,a[45],hp[maxn],ans;
il void dfs1(int x,ll res){
// cout<<x<<" "<<res<<"\n";
if(x>n>>1){
hp[++tot]=res;
return ;
}
dfs1(x+1,res);
dfs1(x+1,res+a[x]);
}
il void dfs2(int x,ll res){
if(x>n){
// cout<<res<<" "<<uprb(hp+1,hp+tot+1,m-res)-hp-1<<"\n";
ans+=uprb(hp+1,hp+tot+1,m-res)-hp-1;
return ;
}
dfs2(x+1,res);
dfs2(x+1,res+a[x]);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dfs1(1,0);
sort(hp+1,hp+tot+1);
dfs2((n>>1)+1,0);
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
2.[NOI2001] 方程的解數(shù)
按照之前的套路，我們首先枚舉前三個(gè)未知數(shù)，存到 map 里，再枚舉后面的未知數(shù)在對應(yīng)的位置查詢即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
int n,m,a[10],b[10],ans;
map<int,int> hp;
il int qpow(int x,int y){
int res=1;
while(y){
if(y&1){
res*=x;
}
x*=x,y>>=1;
}
return res;
}
il void dfs1(int x,int res){
if(x>n>>1){
hp[res]++;
return ;
}
for(int i=1;i<=m;i++){
dfs1(x+1,res+a[x]*qpow(i,b[x]));
}
}
il void dfs2(int x,int res){
if(x>n){
ans+=hp[-res];
return ;
}
for(int i=1;i<=m;i++){
dfs2(x+1,res+a[x]*qpow(i,b[x]));
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
dfs1(1,0);
dfs2((n>>1)+1,0);
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
3.[USACO12OPEN] Balanced Cow Subsets G
依然是老套路，先搜前一半，再搜后一半，存儲(chǔ)兩個(gè)集合之差，判斷每一種選法是否成立。需要狀壓。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=(1<<20)+5,maxm=6e4+5;
int n,a[25],cnt;
bool vis[maxn];
map<int,int> hao;
vector<int> cun[maxm];
il void dfs1(int x,int sta,int res){
if(x>n>>1){
if(!hao.count(res)){
hao[res]=++cnt;
}
int p=hao[res];
cun[p].pb(sta);
return ;
}
dfs1(x+1,sta,res);
dfs1(x+1,sta|1<<(x-1),res+a[x]);
dfs1(x+1,sta|1<<(x-1),res-a[x]);
}
il void dfs2(int x,int sta,int res){
if(x>n){
if(hao.count(res)){
for(int S:cun[hao[res]]){
vis[sta|S]=1;
}
}
return ;
}
dfs2(x+1,sta,res);
dfs2(x+1,sta|1<<(x-1),res+a[x]);
dfs2(x+1,sta|1<<(x-1),res-a[x]);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dfs1(1,0,0);
dfs2(n/2+1,0,0);
int ans=0;
for(int i=1;i<1<<n;i++){
ans+=vis[i];
}
cout<<ans;
return 0;
}
}
signed main(){return asbt::main();}
4.[USACO09NOV] Lights G
對于每個(gè)點(diǎn)，狀壓記錄它會(huì)影響的點(diǎn)。折半搜時(shí)用 map 存答案即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=40;
int n,m,ans=1e9;
ll sta[maxn];
map<ll,int> hua;
il void dfs1(int x,int res,ll S){
if(x>n>>1){
if(!hua.count(S)){
hua[S]=res;
}
else if(hua[S]>res){
hua[S]=res;
}
return ;
}
dfs1(x+1,res+1,S^sta[x]);
dfs1(x+1,res,S);
}
il void dfs2(int x,int res,ll S){
if(x>n){
ll nS=((1ll<<n)-1)^S;
if(hua.count(nS)){
ans=min(ans,hua[nS]+res);
}
return ;
}
dfs2(x+1,res+1,S^sta[x]);
dfs2(x+1,res,S);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
sta[i]|=1ll<<(i-1);
}
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
sta[u]|=1ll<<(v-1);
sta[v]|=1ll<<(u-1);
}
dfs1(1,0,0);
dfs2(n/2+1,0,0);
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
5.[abc184_f]Programming Contest
依然是熟悉的套路。排序后二分即可。注意后一半如果超過了限制就不能二分了。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define uprb upper_bound
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=(1<<20)+5;
int n,m,a[45],hp[maxn],cnt,ans;
il void dfs1(int x,int res){
if(x>n>>1){
hp[++cnt]=res;
return ;
}
dfs1(x+1,res);
dfs1(x+1,res+a[x]);
}
il void dfs2(int x,int res){
if(res>m){
return ;
}
if(x>n){
ans=max(ans,res+*(uprb(hp+1,hp+cnt+1,m-res)-1));
return ;
}
dfs2(x+1,res);
dfs2(x+1,res+a[x]);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dfs1(1,0);
sort(hp+1,hp+cnt+1);
dfs2(n/2+1,0);
cout<<ans;
return 0;
}
}
signed main(){return asbt::main();}
浙公網(wǎng)安備 33010602011771號(hào)