定西市城乡建设局网站,查询公司营业执照的网站,无锡建设管理服务中心,广东新闻联播片头题目 链接
参考代码
写了两个#xff0c;一个是很久以前写的#xff0c;一个是最近刚写的#xff0c;很久以前写的时候还不会数位dp所以写了比较详细的注释#xff0c;这两个代码主要是设置了不同的记忆数组#xff0c;通过这两个代码可以理解记忆数组设置的灵活性。 im…题目 链接
参考代码
写了两个一个是很久以前写的一个是最近刚写的很久以前写的时候还不会数位dp所以写了比较详细的注释这两个代码主要是设置了不同的记忆数组通过这两个代码可以理解记忆数组设置的灵活性。 import java.util.Scanner;public class Main {// 给定两个正整数a和b求在[a,b]中的所有整数中每个数码(digit)各出现了多少次。static int[] b new int[15];static long[][][] f new long[15][10][15];public static void main(String[] args) {Scanner scanner new Scanner(System.in);long n scanner.nextLong();long m scanner.nextLong();for (int i 0; i 15; i) {for (int j 0; j 10; j) {for (int j2 0; j2 15; j2) {f[i][j][j2] -1;}}}for (int i 0; i 9; i) {System.out.print((get(m, i) - get(n - 1, i)) );}}private static long get(long x, int target) {// TODO Auto-generated method stublong t x;int i 0;while (t 0) {b[i] (int) (t % 10);t t / 10;}return dfs(target, true, true, i - 1, 0);}// target 表示要计算的值
// e 是否贴上界
//当要判断的数的位数小于原数的位数时就没有上界了如果位数和原数一样每一位的上界就是对应的原数
// first 是否是数的第一个位
// k 数的第几位 now
// t 出现的次数private static long dfs(int target, boolean e, boolean first, int k, int t) {// TODO Auto-generated method stub//long res 0;if (k -1)return t;// 如果数位考虑完返回出现的次数// f[k][target][t]时公用的找这个x的时候可以用找下一个x的时候也可以用所以他应该具有普遍性// 但是当我的位数和x一样时他有不同的边界if ((!e) (!first) f[k][target][t] ! -1)return f[k][target][t];// 判断这一位我可以最大填到哪个数int u e ? b[k] : 9;// 如果是要填写首位数那么这个数等于0的时候其实位数是减一要单独考虑。if (first) {res dfs(target, false, true, k - 1, t);}// 注意我已经判断了如果要给首位填数首位数为0的情况所以当要给首位填数时我要从1开始如果不是首位那么从0开始即可for (int i first ? 1 : 0; i u; i) {// 贴上界是指此时的位数的上界是受此位的数的限制最大数可能到达不了9// 只有本位是贴上界的下一位才有贴上界的可能比如54321只要是第五位他的上界就是5也就是此位最大取到5// 这也就是为什么在get中一开始遍历的时候e true// 当确定了这个数是5位的时候如果第五位小于5那他后面的数是不贴上界的最大值可以写到9但如果第五位等于5// 那下一位也是贴上界的最大值只能取到4// (i u) e 这也是它的来源res dfs(target, (i u) e, false, k - 1, (i target) ? t 1 : t);}// f[k][target][t]时公用的找这个x的时候可以用找下一个x的时候也可以用,所以他应该具有普遍性// 但是当我的位数和x一样时他有不同的边界限制此时他得出的值具有个性不能给其他的x用所以不能存在f数组中// 这是为什么要判断是否贴上界的原因// 当该位数为一个数的首位时因为此时该数的实际位数是不确定的首位为0时实际位数会减少但我依然记录在res中这样此时的// (f[k][target][t] 就有两种情况一是k是首位的时候二是k不是首位的时候所以我们应该舍去k时首位的时候if (!e !first) {f[k][target][t] res;}return res;}
}
import java.util.Arrays;
import java.util.Scanner;public class 数字计数 {static long dp[][][][] new long[15][10][15][2];
public static void main(String[] args) {Scanner scanner new Scanner(System.in);long a scanner.nextLong();long b scanner.nextLong();for(int i 0;i 15;i)for(int j 0;j 10;j)for(int k 0;k 15;k)Arrays.fill(dp[i][j][k], -1);for(int i 0;i 10;i)System.out.print(solve(b,i)-solve(a-1,i) );//20 21 2 12 22 32 42 52 62 72 82 92 23 24 25 26 27 28 29
// System.out.println(solve(b, 2));//2 12 20-29(10) 32 42 52 62 72 82 92 22
}
static int nums[] new int[15];
static int temp[] new int[15];
static int tot 0;
private static long solve(long n,int k) {// TODO Auto-generated method stubtot0;while(n 0) {nums[tot] (int) (n % 10);n / 10;}return dfs(tot,1,1,k,0);
}
private static long dfs(int cnt, int limit, int zeros, int k, int num) {// TODO Auto-generated method stubif (cnt0) {
// for(int i 1;i 2;i) System.out.print(temp[i]);
// System.out.println( num);return num;}if(limit0dp[cnt][k][num][zeros]!-1) return dp[cnt][k][num][zeros];int up limit1?nums[cnt]:9;int st zeros1?1:0;long res 0;if(zeros1) resdfs(cnt-1, (0up?1:0)limit, 1, k, num);//该位填0for(int i st;i up;i) {
// temp[cnt]i;resdfs(cnt-1, (iup?1:0)limit, 0, k, ik?num1:num);}if(limit0) dp[cnt][k][num][zeros]res;return res;
}
}
