当前位置：首页 > news >正文

CF912E

news 2025/8/18 7:34:10

题目
#算法/进阶搜索
一道相似题
折半搜索,meet-in-the-middle

这题看不懂题目什么意思,看了看题解求:在给定的集合中任选不限定个数,选择的数可以相同,求第k小的数,这里也可以什么都不选,什么不选的时候答案为1

思路:
根据题目,n最大为16,值最大为1e18,如果将值全部存在数组中是存不下的,那么,我们就可以考虑折半查找,如何进行折半查找呢?我们可以将奇数位值得结果存在一起,在将偶数位的结果存在一起,这样就会得出两个集合,之后,我们二分一个数X,寻找集合A与集合B相乘小于等于X的个数,我们以第一个集合A为基准,每次查找集合B中,使得集合A的数乘上集合B的数小于等于X,每查找一个B,就将B的下标加起来,最终个数就等于所有下标的总和.
如果总和大于k,就将右侧的边界放缩,如果小于k就将左边的边界放大

dfs步骤有点不好想,dfs作用就是使得每一个数从x下标开始,到最后一个坐标为止,将所有的数随便组合(可以重复),得出所有的值小于maxVal的情况

void dfs1(int x,ll u){A[++lena]=u;if(x>n)return;for(ll i=1;;i*=a[x]){if(maxVal/i<u)break;dfs1(x+2,i*u);}
}

#include<iostream>#include<string>#include<algorithm>using namespace std;typedef long long ll;ll a[22];ll A[5050000];ll B[5000010];int lena;int lenb;const ll maxVal=1e18;int n;void dfs1(int x,ll u){A[++lena]=u;if(x>n)return;for(ll i=1;;i*=a[x]){if(maxVal/i<u)break;dfs1(x+2,i*u);}}void dfs2(int x,ll u){B[++lenb]=u;if(x>n)return;for(ll i=1;;i*=a[x]){if(maxVal/i<u)break;dfs2(x+2,i*u);}}ll check(ll x){ll  res=0;int j=lenb;for(int i=1;i<=lena;i++){//if(A[i]>x)break;while(j>0&&x/A[i]<B[j])j--;res+=j;}return res;}int main(void){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int k;cin>>k;sort(a+1,a+1+n);  dfs1(1,1);dfs2(2,1);//  cout<<lena<<" "<<lenb<<endl;sort(A+1,A+1+lena);sort(B+1,B+1+lenb);lena=unique(A+1,A+1+lena)-A-1;lenb=unique(B+1,B+1+lenb)-B-1;ll l=1;ll r=1e18;ll ans=0;// cout<<lena<<" "<<lenb<<endl;while(l<=r){ll mid=l+r>>1;if(check(mid)>=k){r=mid-1;ans=mid;}else{l=mid+1;    }}cout<<ans<<endl;}