用python来做这个题目,还真好玩!

bskay

楼主也没有代码，这个是在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-9]) == 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次方，这种数量级决定了几乎只有贪心、动规等少数几种方法有效。

最后就是，这种算法在工作中的应用不是特别广，不理解的话也无所谓。另外，代码就不贴了，细节太多不一定写的对囧

r2007

赞一个。
对于这个题目，f和F函数可以不用构造，直接用参数就能计算出来。公式可以推导出来，应该是O(1)的。
后半部分的逐位尝试是个好思路，把字典排序隐含在尝试过程中，我一直没找到好思路，楼上的这个方法是完善的。

bskay

觉得他的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)来表示,和定义不一致

r2007

细节需要仔细考虑，方向是对的。另外F用递归把所有的都算出来效率更高，我设想的直接公式求F效率低，原因是求解过程中要多次用到不同的F，综合算查表法更好。

substr函数

回复 24# r2007


    楼主有代码可以放

rubyish

perl

1. my ( $K, $N ) = ( 5,       2060 );             # 0.011s
   
2. my ( $K, $N ) = ( 5,       100 );              # 0.01s
   
3. my ( $K, $N ) = ( 15223,   30000000 );         # 0.23s
   
4. my ( $K, $N ) = ( 555555,  10000000 );         # 1.1s
   
5. my ( $K, $N ) = ( 555555,  123456789 );        # 9.6s
   
6. my ( $K, $N ) = ( 12345,   100000000000 );     # 9.97s
   
7. my ( $K, $N ) = ( 543210,  1005006700 );       # 2.65s
   
8. my ( $K, $N ) = ( 2000000, 100000000000000 );  # 18.6s
   
9. my ( $K, $N ) = ( 1230000, 12300000000000 );   # 9.0s
   
10. my ( $K, $N ) = ( 999999,  10000000 );         # 0.38s
    
11. my ( $K, $N ) = ( 9999999999999,  10000000000000 );  # 0.018s
    
12. my ( $K, $N ) = ( 123456781,      123456789 );       # 8.9s

复制代码

1. #!/usr/bin/perl
   
2. 
   
3. my ( $K, $N ) = ( 15223,   30000000 );    # 0.24s
   
4. #my ( $K, $N ) = ( 125711,  3436783320 );  # 7.5s
   
5. 
   
6. sub tellen {
   
7.     my ( $getal, $doorgaan, $serie, $staart ) = @_;
   
8. 
   
9.     if ( @_ == 1 ) {
   
10.         return (1) x $getal if $getal < 10;
    
11.         $getal    = [ map int, split //, $getal ];
    
12.         $doorgaan = @$getal - 2;
    
13.         $serie    = [ (1) x 9 ];
    
14.     }
    
15. 
    
16.     my ( $kleine, $grote, @tweeling, @schaduw ) = ( 0, 0 );
    
17.     my @tien =
    
18.       ( $serie, map [ (0) x ( $_ - 1 ), 1, @$serie ], 1 .. 9 );
    
19. 
    
20.     if ( $getal->[$doorgaan] ) {
    
21.         $kleine += $getal->[$_] for 0 .. $doorgaan - 1;
    
22.         $grote = $getal->[$doorgaan] - 1 + $kleine;
    
23.         $kleine += 1 if not $doorgaan;
    
24.         @tweeling =
    
25.           map [ (0) x ( $_ - 1 ), 1, @$serie ], $kleine .. $grote;
    
26. 
    
27.         my $einde = @tweeling ? $#{ $tweeling[-1] } : -1;
    
28. 
    
29.         @schaduw = map {
    
30.             my ( $i, $toevoeging ) = $_;
    
31.             $toevoeging += $tweeling[$_][$i] || 0 for 0 .. $#tweeling;
    
32.             $toevoeging
    
33.         } 0 .. $einde;
    
34. 
    
35.         $staart->[$_] += $schaduw[$_] for 0 .. $#schaduw;
    
36.     }
    
37. 
    
38.     if ( not $doorgaan ) {
    
39.         my $i = -1;
    
40. 
    
41.         $i           += $getal->[$_]  for 0 .. $#{$getal} - 1;
    
42.         $serie->[$_] += $staart->[$_] for 0 .. $#{$staart};
    
43.         $serie->[$_] += 1             for $i .. $i + $getal->[-1];
    
44.         return @$serie;
    
45.     }
    
46. 
    
47.     $serie = [
    
48.         map {
    
49.             my ( $i, $toevoeging ) = $_;
    
50.             $toevoeging += $tien[$_][$i] || 0 for 0 .. 9;
    
51.             $toevoeging
    
52.         } 0 .. $#{ $tien[-1] }
    
53.     ];
    
54. 
    
55.     tellen( $getal, --$doorgaan, $serie, $staart );
    
56. }
    
57. 
    
58. sub rekenen {
    
59.     my ( $pionier, $tal, $limiet ) = @_;
    
60. 
    
61.     if ( $pionier == 1 ) {
    
62.         return 0 if $tal > 9;
    
63.         return $limiet ? $tal <= $limiet->[0] ? 1 : 0 : 1;
    
64.     }
    
65. 
    
66.     my $voorsp = $pionier - 1;
    
67.     my $kleine = $tal - $voorsp * 9;
    
68.     my $grote  = $tal > 9 ? 9 : $tal;
    
69.     my @mij;
    
70. 
    
71.     $kleine = 0 if $kleine < 0;
    
72. 
    
73.     if ($limiet) {
    
74.         my $maximale = shift @$limiet;
    
75.         $grote = $maximale if $grote > $maximale;
    
76.         @mij = ( (undef) x ( $grote - $kleine ), $limiet );
    
77.     }
    
78. 
    
79.     my $aantal = 0;
    
80.     $aantal += rekenen( $voorsp, $tal - $_, shift @mij )
    
81.       for $kleine .. $grote;
    
82. 
    
83.     return $aantal;
    
84. }
    
85. 
    
86. sub genereren {
    
87.     my ( $pionier, $tal, $limiet ) = @_;
    
88. 
    
89.     if ( $pionier == 1 ) {
    
90.         return if $tal > 9;
    
91.         return $limiet ? $tal <= $limiet->[0] ? $tal : () : $tal;
    
92.     }
    
93. 
    
94.     my $voorsp = $pionier - 1;
    
95.     my $kleine = $tal - $voorsp * 9;
    
96.     my $grote  = $tal > 9 ? 9 : $tal;
    
97.     my @mij;
    
98. 
    
99.     $kleine = 0 if $kleine < 0;
    
100. 
     
101.     if ($limiet) {
     
102.         my $maximale = shift @$limiet;
     
103.         $grote = $maximale if $grote > $maximale;
     
104.         @mij = ( (undef) x ( $grote - $kleine ), $limiet );
     
105.     }
     
106. 
     
107.     map {
     
108.         my $deze = $_;
     
109.         map 10**$voorsp * $deze + $_,
     
110.           genereren( $voorsp, $tal - $deze, shift @mij )
     
111.     } $kleine .. $grote;
     
112. }
     
113. 
     
114. printf "%20s = %s\n", 'N', $N;
     
115. printf "%20s = %s\n", 'K', $K;
     
116. 
     
117. my ( $plaats, $aantal ) = ( 0, 0 );
     
118. my @K       = split //, $K;
     
119. my @N       = map int, split //, $N;
     
120. my $pionier = @N;
     
121. my @element = tellen $N;
     
122. my $groei   = 0;
     
123. 
     
124. $aantal += $_ for @K;
     
125. $plaats += $_ for @element[ 0 .. $aantal - 2 ];
     
126. 
     
127. for my $i ( 1 .. $K[0] ) {
     
128.     my $I = $i == $N[0] ? [ @N[ 1 .. $#N ] ] : undef;
     
129.     my $tal = $aantal - $i;
     
130. 
     
131.     if ( $i < $K[0] ) {
     
132.         my @serie = map { rekenen( $_, $tal ) } 1 .. @N - 2;
     
133.         push @serie, rekenen( $#N, $tal, $I ) if $i <= $N[0];
     
134. 
     
135.         $plaats += $_ for @serie;
     
136.         $plaats += 1 if $aantal == $i;
     
137.     }
     
138.     else {
     
139.         my @serie = map {
     
140.             my $p = $_;
     
141.             map { $i * 10**$p + $_ } genereren( $_, $tal )
     
142.         } 1 .. @N - 2;
     
143. 
     
144.         push @serie, map { $i * 10**$#N + $_ } genereren( $#N, $tal, $I )
     
145.           if $i <= $N[0];
     
146. 
     
147.         unshift @serie, $aantal if $aantal == $i;
     
148.         $plaats += @serie;
     
149. 
     
150.         for my $k ( sort @serie ) {
     
151.             $K == $k ? ( $plaats -= @serie ) && last : $plaats++;
     
152.         }
     
153.     }
     
154. }
     
155. 
     
156. $aantal = 1;
     
157. ( $groei += $_ ) > $K ? last : $aantal++ for @element;
     
158. $groei -= $element[ $aantal - 1 ];
     
159. 
     
160. deze: for my $i ( 1 .. 9 ) {
     
161. 
     
162.     my @serie = map { rekenen( $_, $aantal - $i ) } 1 .. @N - 2;
     
163.     if ( $i <= $N[0] ) {
     
164.         my $I = $i == $N[0] ? [ @N[ 1 .. $#N ] ] : undef;
     
165.         push @serie, rekenen( $#N, $aantal - $i, $I );
     
166.     }
     
167. 
     
168.     my $serie = 0;
     
169.     $serie += $_ for @serie;
     
170.     $serie += 1 if $aantal == $i;
     
171. 
     
172.     next if ( $groei += $serie ) < $K;
     
173.     $groei -= $serie;
     
174. 
     
175.     @serie = map {
     
176.         my $p = $_;
     
177.         map { $i * 10**$p + $_ } genereren( $_, $aantal - $i )
     
178.     } 1 .. @N - 2;
     
179. 
     
180.     if ( $i <= $N[0] ) {
     
181.         my $I = $i == $N[0] ? [ @N[ 1 .. $#N ] ] : undef;
     
182.         push @serie,
     
183.           map { $i * 10**$#N + $_ } genereren( $#N, $aantal - $i, $I );
     
184.     }
     
185. 
     
186.     unshift @serie, $aantal if $aantal == $i;
     
187. 
     
188.     for my $k ( sort @serie ) {
     
189.         ( $groei = $k ) && last deze if $K == $groei++;
     
190.     }
     
191. }
     
192. 
     
193. printf "%20s = %s\n", "index [ $plaats ]", $K;
     
194. printf "%20s = %s\n", "index [ $K ]",      $groei;
     
195. 
     

复制代码