本文主要是介绍2013省赛选拔，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Sum of Digits http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4165 求一段区间有多少个数每一位加起来的和是s，并且求出最小的一个。 数位dp求个数，模拟求最小的数。package net.smgui.common;
import java.util.Arrays;
import java.util.Scanner;
/**
* main
*
* @author FD
* @date 2016/3/24 0024
*/
public class Main {
static long[][][] dp;
static long[] A;
static long N;
public static long dfs(int x, int k, int s, boolean flag) {
if (x == -1) {
return s == N ? 1 : 0;
}
if (!flag && dp[x][k][s] != -1) {
return dp[x][k][s];
}
long end;
if(flag)
end = A[x];
else
end = 9;
long ans = 0;
for (int i = 0; i <= end; i++) {
if (s+i <= N) {
ans += dfs(x-1, i, s+i, flag&&i == end);
}
}
if(!flag)
dp[x][k][s] = ans;
return ans;
}
public static long cal(long x) {
if(x == 0)
return 0;
int l = 0;
while(x > 0)
{
A[l++] = x%10;
x /= 10;
}
return dfs(l-1, 0, 0, Boolean.TRUE);
}
public static long getSum(long res) {
long ans = 0;
while (res > 0) {
ans += res%10;
res /= 10;
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long a, b, n;
a = sc.nextLong();
b = sc.nextLong();
n = sc.nextLong();
N = n;
long nn = n, aa = a;
long ans = a;
int sum = 0;
while (a > 0) {
sum += a%10;
a /= 10;
}
n -= sum;
long m = ans;
long k = 1;
if (n > 0) {
while (n > 0) {
long tmp = m%10;
m /= 10;
if (n < (9-tmp)) {
ans += n*k;
break;
}
else {
ans += (9-tmp)*k;
n -= 9-tmp;
}
k *= 10;
}
}
else {
while (n < 0) {
long tmp = m%10;
if (tmp == 0) {
n = nn-getSum(ans);
m /= 10;
k *= 10;
continue;
}
if (-n <= tmp) {
ans -= (-n)*k;
if (ans < aa) {
ans += k*10;
}
n = nn-getSum(ans);
}
else {
ans -= tmp*k;
if (ans < aa) {
ans += k*10;
}
n = nn-getSum(ans);
m /= 10;
k *= 10;
}
}
k = 1;
m = ans;
if (n > 0) {
while (n > 0) {
long tmp = m%10;
m /= 10;
if (n < (9-tmp)) {
ans += n*k;
break;
}
else {
ans += (9-tmp)*k;
n -= 9-tmp;
}
k *= 10;
}
}
}
dp = new long[20][10][140];
A = new long[20];
for (int i = 0; i < 20; i++) {
for(int j = 0; j < 10; j++) {
Arrays.fill(dp[i][j], -1);
}
}
long ans2 = cal(b)-cal(aa);
System.out.println(ans2);
System.out.println(ans);
// for (int i = 0; i < 10; i++) {
// System.out.println(i + " " + dp[0][0][i]);
// }
}
}这篇关于2013省赛选拔的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
