是个以前没见过的模板题..
我用比较复杂度方式过掉了..
构造一个十叉树 (有点 trie 的味道) 来存数字, 然后字典序就是先序遍历的结果
- #include<bits/stdc++.h>
- using namespace std;
- #define maxn 1000005
- int size[maxn],k,n,th,ans,flag;
- void dfs(int i){
- if(flag)return;
- size[i]=1;
- th++;
- if(th==k)ans=i,flag=1;
- //cout<<i<<endl;
- if(i==0){
- for(int j=1;j<=9;j++)
- if(j<=n)dfs(j);
- }
- else {
- for(int j=0;j<=9;j++){
- int tmp=i*10+j;
- if(tmp<=n){
- dfs(tmp);
- size[i]+=size[tmp];
- }
- else return;
- }
- }
- }
- int main(){
- int t;
- cin>>t;
- while(t--){
- th=-1;flag=0;
- scanf("%d%d",&n,&k);
- dfs(0);
- cout<<ans<<endl;
- }
- }
来源: http://www.bubuko.com/infodetail-2992169.html