折半搜索[世界冰球模拟赛,cow balance,prime gift] | Hexo

归档于 2019-10-14 12:17

好歹做了几道题,

算是一种套路,

看到可以搜索做,然而范围比较大,指数上/2刚好可以,那么无脑折半搜索就可以了

一般来说难点在拼接上,主要讲拼接

世界冰球模拟赛

题意

$n<=40,c<=1e18$的背包,

题解

算是一道裸题,

前20搜索出来,后20搜索出来,

拼接的话,设前一段代价x,后一段代价y,所有(x+y)<=c都可以组成一种方案

排序后lower_bound一下就好了

    for(ll i=1;i<=cnta;i++){
        ans+=1ll*(upper_bound(sumb+1,sumb+cntb+1,m-suma[i])-sumb-1);
    }

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 11111111
ll n,m,cnta=0,cntb=0,ans=0;
ll suma[A],sumb[A],a[A];
void dfs(ll x,ll sum,ll opt){
//    printf("x=%lld sum=%lld opt=%lld n/2=%lld\n",x,sum,opt,n/2);
    if(opt==0){
        if(x>n/2){
            suma[++cnta]=sum;
            return ;
        }
    }
    if(opt){
        if(x>n){
            sumb[++cntb]=sum;
            return ;
        }
    }
    dfs(x+1,sum+a[x],opt);
    dfs(x+1,sum,opt);
}

int main(){
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    dfs(1,0,0);
    dfs(n/2+1,0,1);
    sort(suma+1,suma+cnta+1);
    sort(sumb+1,sumb+cntb+1);
/*
    for(ll i=1;i<=cnta;i++)
        printf("suma=%lld\n",suma[i]);
    for(ll i=1;i<=cntb;i++)
        printf("sumb=%lld\n",sumb[i]);
*/    
    for(ll i=1;i<=cnta;i++){
        ans+=1ll*(upper_bound(sumb+1,sumb+cntb+1,m-suma[i])-sumb-1);
    }
    printf("%lld\n",ans);
}

View Code

prime gift

题意

给定一个大小为n的素数集合

求出分解后只含这些质数因子的第k小整数

$n<=16$

题解

暴力$n!$

折半搜索,+二分答案,看到第k小就二分答案吧

拼接比较简单

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 11111111
ll cnta,cntb,q,k,n;
ll suma[A],sumb[A],a[A];
void dfs1(ll x,ll s){
    if(x>n){suma[++cnta]=s;return;}
    for(ll w=1;;w*=a[x]){dfs1(x+2,s*w);if(1e18/a[x]<w*s)break;}
}
void dfs2(ll x,ll s){
    if(x>n){sumb[++cntb]=s;return;}
    for(ll w=1;;w*=a[x]){dfs2(x+2,s*w);if(1e18/a[x]<w*s)break;}
}
int main(){
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    dfs1(1,1);
    dfs2(2,1);
    sort(suma+1,suma+cnta+1);
    sort(sumb+1,sumb+cntb+1);
    scanf("%lld",&k);
    ll l=0,r=1e18,ans;
    while(l<=r){
        ll mid=(l+r)>>1,tot=0;
        for(ll i=1,p=cntb;i<=cnta;i++,tot+=p)
            while(p&&mid/suma[i]<sumb[p])p--;
        if(tot<k)l=mid+1;
        else{ans=mid;r=mid-1;}
    }
    printf("%lld\n",ans);
}

View Code

cow balance

题意

有多少非空子集能划分成相等两部分

$n<=20$

题解

折半搜索比较简单,但拼接不好拼接,你可能会算少

例如a[1]=15 a[2]=15 a[3]=3

分成可以1划分成一组2,3划分成一组,1,3划分成一组,2划分成一组

这样会有两个贡献,如果再用之前思想只会算一遍

,用状压思想,记录口那些用了,口那些没用,

之后再进行拼接得到最终结果,

拼接部分可以hash表或者双指针

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 11111111
ll n,m,cnta=0,cntb=0,ans=0;
ll a[A];
bool vis[A];
struct node{
    ll state,x;
    node(){}
    node(const ll &a,const ll &b){state=a,x=b;}
}suma[A],sumb[A];
bool cmp1(const node &a,const node &b){
    return a.x<b.x;
}
bool cmp2(const node &a,const node &b){
    return a.x>b.x;
}
void dfs(ll x,ll sum,ll now,ll opt){
    if(opt==0){
        if(x>n/2){
            suma[++cnta]=node(now,sum);
            return ;
        }
    }
    if(opt){
        if(x>n){
            sumb[++cntb]=node(now,sum);
            return ;
        }
    }
    dfs(x+1,sum,now,opt);
    dfs(x+1,sum+a[x],now|(1<<(x-1)),opt);
    dfs(x+1,sum-a[x],now|(1<<(x-1)),opt);
}
int main(){
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    dfs(1,0,0,0);
    dfs(n/2+1,0,0,1);
    sort(suma+1,suma+cnta+1,cmp1);
    sort(sumb+1,sumb+cntb+1,cmp2);
/*
    for(ll i=1;i<=cnta;i++){
        printf("1%lld\n",suma[i].x);
    }
    for(ll i=1;i<=cntb;i++){
        printf("2%lld\n",sumb[i].x);
    }
*/    
    ll r=1;
    for(ll l=1;l<=cnta;l++){
        while(-suma[l].x<sumb[r].x&&r<=cntb) r++;
        ll now=r;
        while(r<=cntb&&-suma[l].x==sumb[r].x){
            if(!vis[suma[l].state|sumb[r].state]){
                vis[suma[l].state|sumb[r].state]=1;
//                printf("vis[%lld]=%lld\n",suma[l].state|sumb[r].state,1ll*vis[suma[l].state|sumb[r].state]);
                ans++;
            }
            r++;
        }
        if(l<cnta&&suma[l].x==suma[l+1].x) r=now;
    }
    printf("%lld\n",ans-1);
}

View Code