楼主也没有代码，这个是在C++版看到一位用动态规划，分析了个开头，但是他也没有分析完全
下面是他的分析（但是距解决问题还很远最多走了20%）：
这道题没办法用模拟的方法的。必须要动态规划加构造。
首先问自己这样的一个问题：假设我们不考虑n的大小，我们构建一个函数f(x, y)，设这个函数的值是：对于一个长度为x的数字，其weight为y的有多少个？
这样的一个函数如何求解呢？
从题设我们知道，x取值在(0~19)（n和k最大1后面18个0，即19位），而y取值在9×18+1（即18位都是9，最高位是1），因此，本质上来说，求解这个函数，就是在填充一个20×163的二维数组。
我们先看这个数组怎么填：
首先，很显然的，如果weight是0，那么无论长度是多少，都只会有一种情况，即：
f(x, 0) == 1
然后，如果长度是0，那么显然一种情况都不会有，即：
f(0, y) == 0
最后，如果长度是1，且y在1～9的范围内，则也最多就一种情况，即：
f(1, ) == 1
这是初始情况。
然后，如果我们要求f(x,y)，应该怎么办呢？我们注意到，对于x位长度的数字，我们要求其权重为y的数字的总数，只需要分别在最高位取1～9（不能是0，这相当于长度只有x-1位），然后我们可以通过f函数得到在这9种情况下的数字总数，将它们加起来就可以了，即：
f(x, y) = f(x-1, y-i) （其中1<=i<=9，且y-i>=0）
由上面的四个方程，我们很容易写出求f函数（或数组）的代码了。这个f是跟n无关的，因此可以复用。
为了方便计算f本身，也是为了方便我们后续的计算，我们还可以定义一个函数F(n,x,y)，这个函数的值为，对于一个x位的数字，如果第一位是n，那么权重为y的数组有多少个。这个函数可以直接定义成一个函数，方便f(x,y)数组本身的计算。
求得f函数，我们很容易通过f函数求得g(weight)函数，即权值为weight的所有数组的总和。注意在求总和的时候，应该考虑n，因此这时需要跟n有关系了。所以，每个不同的n，都需要求得一个不同的g函数（或数组）。具体求法很简单：首先我们遍历n的每一位，假设就从最高位开始吧，比如说n是1236，我们设n(i)是n的第i位数字，比如n(1) == 1，对于最高位取1~n(i)，通过函数F可以得到一系列值，然后对于接下来的每一位，都可以得到一系列值累加到g上，最后我们就可以求得g函数（数组）的值了。
上面有的说f是函数，有的说f是数组，那么f到底是什么呢？实现上，F应该是一个基于f的工具函数，而f和g应该是数组。我们应该按照递推的顺序，逐层地填充这个数组的值。这样的处理手法，就叫动态规划。
有了f，F和g这三个函数，我们可以做什么事情呢？我们就可以构造出题目所需要求的解了。比如“第k位的数字是什么？”，首先我们可以求得这个数组k的权值了。我们对g数组进行累加，直到累加的结果大于k，这时当前累加的是g数组的第几位，则k的weight就应该为多少。然后我们就可以逐步试出k的每一位数组是多少，比如最高位是0吗？如果是0，则加上F(0, x, weight)的数值。反复这样加上去，直到我们算的位数刚刚好就是k，这时我们选取的所有的位数组成的那个数字就是k了，这种一位一位求得答案的方法，就是构造法。
再比如，数字k是第几位？首先可以求得k的weight，那么k的排名肯定不会高于weight比k小的数字。根据g数组很容易得到k的基础排名。现在在相同的weight里面了。利用和上面相同的试验法，我们就可以推出这个排名的精确数字是多少。
另外要注意一些细节：
- 对于数组f，第一位是不能取0的，否则就是x-1位，这点要注意，因此，如果真需要取0（比如不是第一位），那么记得取到f(x,y)时，要加上f(x-1,y)再用。
- 在构造的时候，时刻要当心不要把大于n的数组给构造进去了。这点很容易，当前试验的数字不能超过n当前的位数即可。另外，在操作f(x,y)的时候，也要小心不要加过头了。如果不能保证x位数组都能在1.....0～9.....9取值，则应该用f(x-1, y)累加的方法得到值，避免多加。
这题目，构造出f来，剩下的就是大把的细节问题了，不注重细节很容易出错的。
可以看出这种解题目的方法和你以前了解的应该相差很远，这就是不同于模拟方法的算法方式求解，如果不习惯/适应这种方法，那还是不要看这种题目了。
选择这种方法的一个原因是题目的输入范围，1的18次方，这种数量级决定了几乎只有贪心、动规等少数几种方法有效。
最后就是，这种算法在工作中的应用不是特别广，不理解的话也无所谓。另外，代码就不贴了，细节太多不一定写的对囧
赞一个。:victory:
对于这个题目，f和F函数可以不用构造，直接用参数就能计算出来。公式可以推导出来，应该是O(1)的。
后半部分的逐位尝试是个好思路，把字典排序隐含在尝试过程中，我一直没找到好思路，楼上的这个方法是完善的。
觉得他的F没有定义好
对于一个x位的数字，如果第一位是n，那么权重为y的数组有多少个。
这个看第一位应该不能为0
但是他后面有用到F(0,....
另外
f(x, y) = f(x-1, y-i) （其中1<=i<=9，且y-i>=0）
也有点问题,没有考虑第一位之后就是0的情况,和定义不一致了
比如
10002 5位的
没办法用 f(4,w)来表示,和定义不一致
细节需要仔细考虑，方向是对的。另外F用递归把所有的都算出来效率更高，我设想的直接公式求F效率低，原因是求解过程中要多次用到不同的F，综合算查表法更好。
回复 24# r2007
楼主有代码可以放:hug:
:D) perlmy ( $K, $N ) = ( 5, 2060 ); # 0.011s
my ( $K, $N ) = ( 5, 100 ); # 0.01s
my ( $K, $N ) = ( 15223, 30000000 ); # 0.23s
my ( $K, $N ) = ( 555555,10000000 ); # 1.1s
my ( $K, $N ) = ( 555555,123456789 ); # 9.6s
my ( $K, $N ) = ( 12345, 100000000000 ); # 9.97s
my ( $K, $N ) = ( 543210,1005006700 ); # 2.65s
my ( $K, $N ) = ( 2000000, 100000000000000 );# 18.6s
my ( $K, $N ) = ( 1230000, 12300000000000 ); # 9.0s
my ( $K, $N ) = ( 999999,10000000 ); # 0.38s
my ( $K, $N ) = ( 9999999999999,10000000000000 );# 0.018s
my ( $K, $N ) = ( 123456781, 123456789 ); # 8.9s#!/usr/bin/perl
my ( $K, $N ) = ( 15223, 30000000 ); # 0.24s
#my ( $K, $N ) = ( 125711,3436783320 );# 7.5s
sub tellen {
my ( $getal, $doorgaan, $serie, $staart ) = @_;
if ( @_ == 1 ) {
return (1) x $getal if $getal < 10;
$getal = [ map int, split //, $getal ];
$doorgaan = @$getal - 2;
$serie = [ (1) x 9 ];
}
my ( $kleine, $grote, @tweeling, @schaduw ) = ( 0, 0 );
my @tien =
( $serie, map [ (0) x ( $_ - 1 ), 1, @$serie ], 1 .. 9 );
if ( $getal->[$doorgaan] ) {
$kleine += $getal->[$_] for 0 .. $doorgaan - 1;
$grote = $getal->[$doorgaan] - 1 + $kleine;
$kleine += 1 if not $doorgaan;
@tweeling =
map [ (0) x ( $_ - 1 ), 1, @$serie ], $kleine .. $grote;
my $einde = @tweeling ? $#{ $tweeling[-1] } : -1;
@schaduw = map {
my ( $i, $toevoeging ) = $_;
$toevoeging += $tweeling[$_][$i] || 0 for 0 .. $#tweeling;
$toevoeging
} 0 .. $einde;
$staart->[$_] += $schaduw[$_] for 0 .. $#schaduw;
}
if ( not $doorgaan ) {
my $i = -1;
$i += $getal->[$_]for 0 .. $#{$getal} - 1;
$serie->[$_] += $staart->[$_] for 0 .. $#{$staart};
$serie->[$_] += 1 for $i .. $i + $getal->[-1];
return @$serie;
}
$serie = [
map {
my ( $i, $toevoeging ) = $_;
$toevoeging += $tien[$_][$i] || 0 for 0 .. 9;
$toevoeging
} 0 .. $#{ $tien[-1] }
];
tellen( $getal, --$doorgaan, $serie, $staart );
}
sub rekenen {
my ( $pionier, $tal, $limiet ) = @_;
if ( $pionier == 1 ) {
return 0 if $tal > 9;
return $limiet ? $tal <= $limiet-> ? 1 : 0 : 1;
}
my $voorsp = $pionier - 1;
my $kleine = $tal - $voorsp * 9;
my $grote= $tal > 9 ? 9 : $tal;
my @mij;
$kleine = 0 if $kleine < 0;
if ($limiet) {
my $maximale = shift @$limiet;
$grote = $maximale if $grote > $maximale;
@mij = ( (undef) x ( $grote - $kleine ), $limiet );
}
my $aantal = 0;
$aantal += rekenen( $voorsp, $tal - $_, shift @mij )
for $kleine .. $grote;
return $aantal;
}
sub genereren {
my ( $pionier, $tal, $limiet ) = @_;
if ( $pionier == 1 ) {
return if $tal > 9;
return $limiet ? $tal <= $limiet-> ? $tal : () : $tal;
}
my $voorsp = $pionier - 1;
my $kleine = $tal - $voorsp * 9;
my $grote= $tal > 9 ? 9 : $tal;
my @mij;
$kleine = 0 if $kleine < 0;
if ($limiet) {
my $maximale = shift @$limiet;
$grote = $maximale if $grote > $maximale;
@mij = ( (undef) x ( $grote - $kleine ), $limiet );
}
map {
my $deze = $_;
map 10**$voorsp * $deze + $_,
genereren( $voorsp, $tal - $deze, shift @mij )
} $kleine .. $grote;
}
printf "%20s = %s\n", 'N', $N;
printf "%20s = %s\n", 'K', $K;
my ( $plaats, $aantal ) = ( 0, 0 );
my @K = split //, $K;
my @N = map int, split //, $N;
my $pionier = @N;
my @element = tellen $N;
my $groei = 0;
$aantal += $_ for @K;
$plaats += $_ for @element[ 0 .. $aantal - 2 ];
for my $i ( 1 .. $K ) {
my $I = $i == $N ? [ @N[ 1 .. $#N ] ] : undef;
my $tal = $aantal - $i;
if ( $i < $K ) {
my @serie = map { rekenen( $_, $tal ) } 1 .. @N - 2;
push @serie, rekenen( $#N, $tal, $I ) if $i <= $N;
$plaats += $_ for @serie;
$plaats += 1 if $aantal == $i;
}
else {
my @serie = map {
my $p = $_;
map { $i * 10**$p + $_ } genereren( $_, $tal )
} 1 .. @N - 2;
push @serie, map { $i * 10**$#N + $_ } genereren( $#N, $tal, $I )
if $i <= $N;
unshift @serie, $aantal if $aantal == $i;
$plaats += @serie;
for my $k ( sort @serie ) {
$K == $k ? ( $plaats -= @serie ) && last : $plaats++;
}
}
}
$aantal = 1;
( $groei += $_ ) > $K ? last : $aantal++ for @element;
$groei -= $element[ $aantal - 1 ];
deze: for my $i ( 1 .. 9 ) {
my @serie = map { rekenen( $_, $aantal - $i ) } 1 .. @N - 2;
if ( $i <= $N ) {
my $I = $i == $N ? [ @N[ 1 .. $#N ] ] : undef;
push @serie, rekenen( $#N, $aantal - $i, $I );
}
my $serie = 0;
$serie += $_ for @serie;
$serie += 1 if $aantal == $i;
next if ( $groei += $serie ) < $K;
$groei -= $serie;
@serie = map {
my $p = $_;
map { $i * 10**$p + $_ } genereren( $_, $aantal - $i )
} 1 .. @N - 2;
if ( $i <= $N ) {
my $I = $i == $N ? [ @N[ 1 .. $#N ] ] : undef;
push @serie,
map { $i * 10**$#N + $_ } genereren( $#N, $aantal - $i, $I );
}
unshift @serie, $aantal if $aantal == $i;
for my $k ( sort @serie ) {
( $groei = $k ) && last deze if $K == $groei++;
}
}
printf "%20s = %s\n", "index [ $plaats ]", $K;
printf "%20s = %s\n", "index [ $K ]", $groei;