zyb的面试

Problem Description

今天zyb参加一场面试,面试官听说zyb是ACMer之后立马抛出了一道算法题给zyb:
有一个序列,是1到n的一种排列,排列的顺序是字典序小的在前,那么第k个数字是什么?
例如n=15,k=7, 排列顺序为1, 10, 11, 12, 13, 14, 15, 2, 3, 4, 5, 6, 7, 8, 9;那么第7个数字就是15.
那么,如果你处在zyb的场景下,你能解决这个问题吗?

Input

T组样例(T<=100)
两个整数n和k(1<=n<=1e6,1<=k<=n),n和k代表的含义如上文

Output

输出1-n之中字典序第k小的数字

Sample Input

1
15 7

Sample Output

Source

“字节跳动-文远知行杯”广东工业大学第十四届程序设计竞赛

分析：

考虑写一个函数 $f f (v a l, n)$ 表示字典序中 $1$ ~ $n$ 中按字典序排列小于 $v a l$ 的数有多少个。

然后dfs搜索，求答案的第 $p$ 位是多少, 下面描述dfs的思路

用 $d f s (p)$ 表示现在正在求答案的第 $p$ 位，用 $d i g i t$ 数组来存储 $v a l$ 已经确定的前 $p - 1 $ 位，
现在求val的第 $p$ 位。令val的第p位 $i$ ( $i$ 的初始值为0)，且 $i$ 的取值范围为(0~9) 。
- 如果此时 $f f (v a l, n) = = k - 1$ 则 $v a l$ 就是答案，返回val即可
- 如果此时 $f f (v a l, n) > k - 1$ ,则 $v a l$ 的第 $p$ 位为 $i - 1$ 。接下来求 $d f s (p + 1)$ 即可
- 如果此时 $f f (v a l, n) < k$ ，将 $i$ 增加 $1$ 。 返回上一步
- 如果 $i = 9$ 且仍然 $f f (v a l, n) < k$ , 则 $v a l$ 的第 $p$ 位为 $9$ ，接下来求 $d f s (p + 1)$ 即可

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
int arr[10],digit[10];
ll Pow10[10],n,k;
void init()
{
    Pow10[0]=1,Pow10[1]=10;
    for(int i=2;i<10;++i) Pow10[i]=Pow10[i-1]*10ll;
}
int getCnt(ll val){
    int tot=0;
    while(val){
        tot++;
        val/=10;
    }
    return tot;
}
ll calc(int top)//在digit中 高位 到底位 top个
{
    ll sum=0;
    for(int i=1;i<=top;++i) sum=sum*10+digit[i];
    return sum;
}
ll ff(ll val,ll n)//求1~n中字典序小于val的有多少个
{
    /*用排列组合的加法原理来求。即一位，二位，三位.....字典序小于val的个数之和*/
     ll Presum=0,Pretot=0;
     int top=0;
     ll mid=val;
     do{
        arr[++top]=mid%10;
        mid/=10;
     }while(mid);
     for(int i=top;i;--i){
        Presum=Presum*10+arr[i];
        Pretot+=Presum-Pow10[top-i];
        if(i!=1)
            Pretot++;
     }
     for(;;){
        top++;
        Presum*=10ll;//23 230 2300 这几个数一定相邻
        if(top<getCnt(n))//val的位数小于n的位数
            Pretot+=Presum-Pow10[top-1];
        else if(top==getCnt(n))//val的位数等于n的位数
        {
            Pretot+=min(Presum,n)-Pow10[top-1];
            if(Presum>n)
                Pretot++;
            return Pretot;
        }
        else
            return Pretot;
     }
     return -1;
}
ll dfs(int pp)
{
    for(int i=0;i<10;++i)
    {
        if(pp==1&&i==0)
            continue;
        digit[pp]=i;
        ll val=calc(pp);
        if(val>n)
            continue;
        ll tot=ff(val,n);
        if(tot==k-1)
            return val;
        if(tot>k-1)
        {
            digit[pp]=i-1;
            return dfs(pp+1);
        }
    }
    //i==9还小于
    digit[pp]=9;
    return dfs(pp+1);
}
int main()
{
    init();
    int t;
    scanf("%d",&t);
    while(t--){
        cin>>n>>k;
        cout<<dfs(1)<<endl;
    }
    return 0;
}

zyb的面试 Hdu6468

zyb的面试

分析：

代码：