2019杭电多校 hdu6659 Acesrc and Good Numbers

http://acm.hdu.edu.cn/showproblem.php?pid=6659

题意：给你d,x，让求满足f(d,n)=n的最大n(n<=x)，其中f(d,n)表示数字d在从1到n的数中出现的总次数。

思路：网上真的是有一种神仙思路（找规律，推公式），显然如果f(d,x)=x那么答案就是x，否则让x -= max( 1 , abs(f(d,x)-x)/18 )然后再验，猛地一看感觉很不靠谱，x是1e18岂不是要爆掉？仔细一看abs(f(d,x)-x)和x的数量级是一样的。。（例如让d=1,x=500，一个500，一个100，至于还有个/18无所谓，因为x越大影响越不明显），这样循环次数就不会很多，/18因为f(d,n-1)和f(d,n)最多差18，然后算f(d,x)算是一个板子，就是依次算个位，十位，百位...

复杂度也会很低。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 ll cal(ll n,ll x){

     ll cnt = ,k;

     for(ll i=;k=n/i;i*=){

         cnt += (k/)*i;

         int cur = k%;

         if(cur>x) cnt += i;

         else if(cur==x) cnt += n-k*i+;

     }

     return cnt;

 }

 int main(){

     ios::sync_with_stdio();

     cin.tie();

     cout.tie();

     int T;

     cin>>T;

     while(T--){

        ll d,x;

        cin>>d>>x;

        while(){

            ll num = cal(x,d);

            if(num == x){

                cout<<x<<endl;

                break;

            }

            x -= max(1LL,abs(num-x)/);

        }

     }

     return ;

 }

巴特西

2019杭电多校 hdu6659 Acesrc and Good Numbers

最新文章

热门文章