P2022 有趣的数(思维+模拟)

题目链接:https://www.luogu.org/problemnew/show/P2022

解题思路:首先这是一道数位DP题(ZOJ官方题解说的)。。。

但是DP我肯定是解不出来的了

于是参考洛谷题解开始强行思维

思维都在注释里

代码

 

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int maxn=123;

long long k,m,bignum,hignum,base;

long long getlow(long long x)
{
    long long cnt=0,base1=1,x1=x,x2=x;
    while(x1)//确定位数
    {
        x1/=10;
        base1*=10;
    }
    base1/=10;
    base=base1;
    while(x2)//累加比x小的,字典序也比x小的数的个数
    {
        cnt+=x2-base1+1;//比如456,第一次循环时是456-100+1,第二次是45-10+1......
        x2/=10;
        base1/=10;
    }
    return cnt;//返回小于等于x并且字典序也小于x的个数
}

int main()
{
    long long k,m;
    cin>>k>>m;
    long long lo=getlow(k);
    m-=lo;
    if(m<0)
        cout<<"0"<<endl;
    else if(m==0)
        cout<<k<<endl;
    else
    {
        for(long long i=1;; i*=10) //确定位数
        {
            if(k/i<10)
            {
                bignum=i;
                hignum=k-i;
                break;
            }
        }
        if(hignum==0)
            cout<<"0"<<endl;
        else
        {
            bignum*=10;
            hignum*=10;//例如456,就从1000开始计算,hignum就是当前数量级上字典序小于k但实际大于k的数量
            while(m>hignum)
            {
                m-=hignum;
                bignum*=10;
                hignum*=10;
            }
            cout<<bignum+m-1<<endl;
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注