好歹做了几道题,
算是一种套路,
看到可以搜索做,然而范围比较大,指数上/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); }
给定一个大小为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); }
原文：https://www.cnblogs.com/znsbc-13/p/11670859.html
