复杂度分析

假设本来是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

巴特西

meet in the middle 折半搜索刷题记录

复杂度分析

洛谷P2962 [USACO09NOV]灯Lights

洛谷P4799 [CEOI2015 Day2]世界冰球锦标赛

最新文章

热门文章

巴特西

meet in the middle 折半搜索 刷题记录

复杂度分析

洛谷P2962 [USACO09NOV]灯Lights

洛谷P4799 [CEOI2015 Day2]世界冰球锦标赛

最新文章

热门文章

meet in the middle 折半搜索刷题记录