@[sheep](/space/show?uid=7419) 不知dalao您用的是什么方法,暴力算不了那么多,而本蒟蒻已经想了1小时了,也没想出什么好方法,打模拟又被细节卡住了,无从下手……
by 这有一只匿 @ 2018-07-28 16:13:00
@[suki_cz](/space/show?uid=21710) 尝试推规律也失败了23333
by 这有一只匿 @ 2018-07-28 16:13:31
我的方法是从上一个数直接构造下一个数。
从低位开始向上构造。
这是我的代码:
```cpp
#include <stdio.h>
#define N 1001
int a[N] = {1, 9}, l = 1;
int main()
{
int i, c = 0, k, s;
scanf("%d", &k);
c = 1, s = 10;
while(c < k){
for(i = l; i >= 0; i--){
if(a[i] == 9){
s -= 9;
a[i] = 0;
continue;
}
a[i]++, s++;
if(s <= 10) break;
s -= a[i], a[i] = 0;
}
if(i < 0){
a[0] = 1, a[++l] = 9, s = 10;
}
else a[l] = 10 - s, s = 10;
c++;
}
for(i = 0; i <= l; i++) printf("%d", a[i]);
return 0;
}
```
by L2_sheep @ 2018-07-28 16:40:08
但是如果k = 10^12时,应该怎么做呢?
by L2_sheep @ 2018-07-28 16:48:37
@[sheep](/space/show?uid=7419) 我算出来答案也是20111220000010
,我用了个傻子二分,感觉复杂度比暴力还要打(怕不是要完……)
by 这有一只匿 @ 2018-07-29 08:23:43
我一开始也是想着直接构造诶,但是~~失败了~~,如果k=1e12的话,可能要打表推规律?
by 这有一只匿 @ 2018-07-29 08:25:22
woc,答案好像要大于1e18……
by 这有一只匿 @ 2018-07-29 08:28:37
k = 10^12, 算出来了。
答案是10000000100000100000100000000000001000000000000100000000010110001000
我用了组合数学的方法。
下面是我的代码:
```
#include <stdio.h>
#define N 81
#define M 11
long long c[N][M] = {1};
int main()
{
int i, j, l, s;
long long k, t = 0;
scanf("%lld", &k);
for(i = 1; i < N; i++){
c[i][0] = 1;
for(j = 1; j < M; j++) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
for(i = 2, j = 11; j < N; i++, j++){
if(c[j][10] - i >= k) break;
t = c[j][10] - i;
}
l = i - 1, s = 10;
for(i = 1; ; i++){
if(t + c[s - i - 1 + l][s - i] >= k) break;
else t += c[s - i - 1 + l][s - i];
}
printf("%d", i);
l--, s -= i;
while(l > 0){
if(s == 0) printf("0");
else{
for(i = 0; ; i++){
if(t + c[s - i - 1 + l][s - i] >= k) break;
else t += c[s - i - 1 + l][s - i];
}
printf("%d", i);
s -= i;
}
l--;
}
printf("%d", s);
return 0;
}
```
by L2_sheep @ 2018-07-29 14:21:21
%%%%orz
by 这有一只匿 @ 2018-07-29 14:29:23