[ARC99D]Snuke Number——神奇打表题

题目大意：

记$S(x)$为$x$各个数位的和，定义一个数为Snuke Number当且仅当任意$y>x$都满足$dfrac{y}{S(y)}geqslant dfrac{x}{S(x)}$。求前$k$个Snuke Number。

思路：

表示这道题看得我一脸懵逼，打了一个表，没发现什么规律，但是别人就发现了：

1
2
3
4
5
6
7
8
9
19
29
39
49
59
69
79
89
99
199
299
399
499
599
699
799
899
999
1099
1199
1299
1399
1499
1599
1699
1799
1899
1999
2999
3999
4999
5999
6999
7999
8999
9999
10999
11999
12999
13999
14999
15999
16999
17999
18999
19999
20999
21999
22999
23999
24999
25999
26999
27999
28999
29999
39999
49999
59999
69999
79999
89999
99999

就是前一个Snuke数可以推后一个Snuke数，因为前一个保证可以加上$10^x$来得到下一个，所以我们便可以枚举 x x <script type="math/tex" id="MathJax-Element-492">x</script>，再来check下一个。
至于怎么check，考虑上面的那个分式，因为要满足所有的后面的都大于前面的，所以我们只要让后面的最小的大于前面的就好了，到了后面，分子必定会增大，但是分母就不一定，所以我们要取分母比现在的大的，一种贪心的方法就是让每一位增加1就好了，因为这样可以保证分子的增加量最小（随便伪证一下）。

/*=============================
 * Author : ylsoi
 * Problem : ARC99D
 * Algorithm : Print The Table
 * Time : 2018.6.24
 * ==========================*/
#include<bits/stdc++.h>

#define REP(i,a,b) for(int i=a;i<=b;++i)
typedef long long ll;

using namespace std;

void File(){
    freopen("ARC99D.in","r",stdin);
    freopen("ARC99D.out","w",stdout);
}

double cal(ll x){
    ll y=10,len=1,sum=0,ret=x;
    while(y<=x)y=(y<<1)+(y<<3),++len;
    while(len--){
        y/=10;
        sum+=x/y;
        x%=y;
    }
    return ret*1.0/sum;
}

bool judge(ll x){
    ll a=1;
    while(a<=x){
        if(cal(x+a)<cal(x))return false;
        a=(a<<1)+(a<<3);
    }
    return true;
}

ll k,now;


int main(){
    File();
    cin>>k;
    while(k--){
        ll a=1;
        while(true){
            if(judge(now+a)){
                now+=a;
                break;
            }
            a=(a<<1)+(a<<3);
        }
        cout<<now<<endl;
    }
    return 0;
}

最后

以上就是爱笑奇异果为你收集整理的[ARC99D]Snuke Number——神奇打表题的全部内容，希望文章能够帮你解决[ARC99D]Snuke Number——神奇打表题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。