复杂度分析
假设本来是n层，本来复杂度是O（2^n），如果meet in middle那就是n/2层，那复杂度变为O（ 2^(n/2) ），跟原来的复杂度相比就相当于开了个方
比如如果n=40那爆搜2^40肯定T飞，那用meet in middle的话就是2^20就可做了。
洛谷P2962 [USACO09NOV]灯Lights
- 灯只有35个，用二进制可以表示所有灯的状态，于是考虑搜索
- 1表示该灯是亮的，0表示是灭的
- 把某一个等和与他相邻的灯的位都置1表示该灯位置的开关，用 li 数组表示，按下开关 i 就相当于异或 li[i]
- map存前半部分能到达的状态下按的最少开关数
- 先爆搜前半部分，更新map，再爆搜后半部分，看其补集是否存在更新答案
- 注意前半部分本来就有不需要按灯的状态，所以cnt一开始都是1，最后ans-2即可
- 基本上抄袭hzwer代码：
#include <bits/stdc++.h> using namespace std;
typedef long long ll;
int n, m, flag=, ans=1e9;
ll x[], li[];
ll e=;
map <ll,int> st; void dfs(int now, ll d, int cnt) {
if(now == n/+ && flag) {
if( st[d]!= ) st[d] = min(st[d], cnt);
else st[d] = cnt;
return;
}
if(now == n+) {
if( st[e-d]!= ) ans = min(ans, st[e-d]+cnt);
return;
}
dfs(now+, d^li[now], cnt+); //按下开关
dfs(now+, d, cnt);
} int main(){
cin >> n >> m;
x[] = ;
for (int i=; i<=n; i++) x[i] = x[i-] << ;
int a, b;
for (int i=; i<m; i++) {
scanf("%d%d", &a, &b);
li[a] ^= x[b];
li[b] ^= x[a];
}
for (int i=; i<=n; i++) { li[i] ^= x[i]; e ^= x[i]; }
dfs(,,);
flag = ;
dfs(n/+,,);
cout << ans- << endl;
return ;
}（＞人＜；）
洛谷P4799 [CEOI2015 Day2]世界冰球锦标赛
- 搜后一半的时候需要知道前一半有多少值小于tmp
- 把前一半的值用数组保存起来，排个序，upperbound就行了
- longlong 打成int调了好久，为什么还是会犯这种很傻的错误呢，害
- 代码：
#include <bits/stdc++.h> using namespace std;
typedef long long ll;
ll n,tot,flag=,ans=,mid,id=;
ll c[];
ll mj[]; void dfs(ll now,ll s){
if(s>tot) return;
if(now==mid && flag){
mj[++id]=s;
return;
}
if(now==n+){
ll tmp=tot-s;
ans+=( upper_bound(mj+, mj+id+, tmp)-mj- );
return;
}
dfs(now+,s+c[now]);
dfs(now+,s);
} int main(){
cin>>n>>tot;
mid=n/+;
for (int i=; i<=n; i++) scanf("%lld",&c[i]);
dfs(,);
sort(mj+,mj+id+);
flag=;
dfs(mid,);
cout<<ans<<endl;
return ;
}qwq