class085 数位dp-下【算法】
code1 P2657 [SCOI2009] windy 数
// windy数
// 不含前导零且相邻两个数字之差至少为2的正整数被称为windy数
// windy想知道[a,b]范围上总共有多少个windy数
// 测试链接 : https://www.luogu.com.cn/problem/P2657
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
package class085;
// windy数
// 不含前导零且相邻两个数字之差至少为2的正整数被称为windy数
// windy想知道[a,b]范围上总共有多少个windy数
// 测试链接 : https://www.luogu.com.cn/problem/P2657
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Code01_WindyNumber {
public static int MAXLEN = 11;
public static int[][][] dp = new int[MAXLEN][11][2];
public static void build(int len) {
for (int i = 0; i <= len; i++) {
for (int j = 0; j <= 10; j++) {
dp[i][j][0] = -1;
dp[i][j][1] = -1;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
int a = (int) in.nval;
in.nextToken();
int b = (int) in.nval;
out.println(compute(a, b));
}
out.flush();
out.close();
br.close();
}
public static int compute(int a, int b) {
return cnt(b) - cnt(a - 1);
}
// 求0~num范围上，windy数的个数
public static int cnt(int num) {
if (num == 0) {
return 1;
}
int len = 1;
int offset = 1;
int tmp = num / 10;
while (tmp > 0) {
len++;
offset *= 10;
tmp /= 10;
}
build(len);
return f(num, offset, len, 10, 0);
}
// offset完全由len决定，为了方便提取num中某一位数字（上节课内容）
// 从num的高位开始，还剩下len位没有决定
// 前一位的数字是pre，如果pre == 10，表示从来没有选择过数字
// 如果之前的位已经确定比num小，那么free == 1，表示接下的数字可以自由选择
// 如果之前的位和num一样，那么free == 0，表示接下的数字不能大于num当前位的数字
// 返回<=num的windy数有多少个
public static int f(int num, int offset, int len, int pre, int free) {
if (len == 0) {
return 1;
}
if (dp[len][pre][free] != -1) {
return dp[len][pre][free];
}
int cur = num / offset % 10;
int ans = 0;
if (free == 0) {
if (pre == 10) {
// 之前的位和num一样，此时不能随意选择数字
// 也从来没有选择过数字
// 就表示：来到的是num的最高位
ans += f(num, offset / 10, len - 1, 10, 1); // 一个数字也不要
for (int i = 1; i < cur; i++) {
ans += f(num, offset / 10, len - 1, i, 1);
}
ans += f(num, offset / 10, len - 1, cur, 0);
} else {
// 之前的位和num一样，此时不能随意选择数字，
// 之前选择过数字pre
for (int i = 0; i <= 9; i++) {
if (i <= pre - 2 || i >= pre + 2) {
if (i < cur) {
ans += f(num, offset / 10, len - 1, i, 1);
} else if (i == cur) {
ans += f(num, offset / 10, len - 1, cur, 0);
}
}
}
}
} else {
if (pre == 10) {
// free == 1，可以自由选择数字，前面的状况 < num
// 从来没有选择过数字
ans += f(num, offset / 10, len - 1, 10, 1); // 还是可以不选择数字
for (int i = 1; i <= 9; i++) {
ans += f(num, offset / 10, len - 1, i, 1);
}
} else {
// free == 1，可以自由选择数字，前面的状况 < num
// 选择过数字pre
for (int i = 0; i <= 9; i++) {
if (i <= pre - 2 || i >= pre + 2) {
ans += f(num, offset / 10, len - 1, i, 1);
}
}
}
}
dp[len][pre][free] = ans;
return ans;
}
}
code2 P3413 SAC#1 - 萌数
// 萌数
// 如果一个数字，存在长度至少为2的回文子串，那么这种数字被称为萌数
// 比如101、110、111、1234321、45568
// 求[l,r]范围上，有多少个萌数
// 由于答案可能很大，所以输出答案对1000000007求余
// 测试链接 : https://www.luogu.com.cn/problem/P3413
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
package class085;
// 萌数
// 如果一个数字，存在长度至少为2的回文子串，那么这种数字被称为萌数
// 比如101、110、111、1234321、45568
// 求[l,r]范围上，有多少个萌数
// 由于答案可能很大，所以输出答案对1000000007求余
// 测试链接 : https://www.luogu.com.cn/problem/P3413
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Code02_MengNumber {
public static int MOD = 1000000007;
public static int MAXN = 1001;
public static int[][][][] dp = new int[MAXN][11][11][2];
public static void build(int n) {
for (int a = 0; a < n; a++) {
for (int b = 0; b <= 10; b++) {
for (int c = 0; c <= 10; c++) {
for (int d = 0; d <= 1; d++) {
dp[a][b][c][d] = -1;
}
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
String[] strs = br.readLine().split(" ");
out.println(compute(strs[0].toCharArray(), strs[1].toCharArray()));
out.flush();
out.close();
br.close();
}
public static int compute(char[] l, char[] r) {
int ans = (cnt(r) - cnt(l) + MOD) % MOD;
if (check(l)) {
ans = (ans + 1) % MOD;
}
return ans;
}
// 返回0~num范围上萌数有多少个
public static int cnt(char[] num) {
if (num[0] == '0') {
return 0;
}
int n = num.length;
long all = 0;
long base = 1;
for (int i = n - 1; i >= 0; i--) {
// 不理解的话看一下，讲解041-同余原理
all = (all + base * (num[i] - '0')) % MOD;
base = (base * 10) % MOD;
}
build(n);
return (int) ((all - f(num, 0, 10, 10, 0) + MOD) % MOD);
}
// 从num的高位开始，当前来到第i位
// 前一位数字是p、前前一位数字是pp，如果值是10，则表示那一位没有选择过数字
// 如果之前的位已经确定比num小，那么free == 1，表示接下的数字可以自由选择
// 如果之前的位和num一样，那么free == 0，表示接下的数字不能大于num当前位的数字
// 返回<=num且不是萌数的数字有多少个
public static int f(char[] num, int i, int pp, int p, int free) {
if (i == num.length) {
return 1;
}
if (dp[i][pp][p][free] != -1) {
return dp[i][pp][p][free];
}
int ans = 0;
if (free == 0) {
if (p == 10) {
// 当前来到的就是num的最高位
ans = (ans + f(num, i + 1, 10, 10, 1)) % MOD; // 当前位不选数字
for (int cur = 1; cur < num[i] - '0'; cur++) {
ans = (ans + f(num, i + 1, p, cur, 1)) % MOD;
}
ans = (ans + f(num, i + 1, p, num[i] - '0', 0)) % MOD;
} else {
// free == 0，之前和num一样，此时不能自由选择数字
// 前一位p，选择过数字，p -> 0 ~ 9
for (int cur = 0; cur < num[i] - '0'; cur++) {
if (pp != cur && p != cur) {
ans = (ans + f(num, i + 1, p, cur, 1)) % MOD;
}
}
if (pp != num[i] - '0' && p != num[i] - '0') {
ans = (ans + f(num, i + 1, p, num[i] - '0', 0)) % MOD;
}
}
} else {
if (p == 10) {
// free == 1，能自由选择数字
// 从来没选过数字
ans = (ans + f(num, i + 1, 10, 10, 1)) % MOD; // 依然不选数字
for (int cur = 1; cur <= 9; cur++) {
ans = (ans + f(num, i + 1, p, cur, 1)) % MOD;
}
} else {
// free == 1，能自由选择数字
// 之前选择过数字
for (int cur = 0; cur <= 9; cur++) {
if (pp != cur && p != cur) {
ans = (ans + f(num, i + 1, p, cur, 1)) % MOD;
}
}
}
}
dp[i][pp][p][free] = ans;
return ans;
}
public static boolean check(char[] num) {
for (int pp = -2, p = -1, i = 0; i < num.length; pp++, p++, i++) {
if (pp >= 0 && num[pp] == num[i]) {
return true;
}
if (p >= 0 && num[p] == num[i]) {
return true;
}
}
return false;
}
}
code3 600. 不含连续1的非负整数
// 不含连续1的非负整数
// 给定一个正整数n，请你统计在[0, n]范围的非负整数中
// 有多少个整数的二进制表示中不存在连续的1
// 测试链接 : https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/
package class085;
// 不含连续1的非负整数
// 给定一个正整数n，请你统计在[0, n]范围的非负整数中
// 有多少个整数的二进制表示中不存在连续的1
// 测试链接 : https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/
public class Code03_IntegersWithoutConsecutiveOnes {
public static int findIntegers1(int n) {
int[] cnt = new int[31];
cnt[0] = 1;
cnt[1] = 2;
for (int len = 2; len <= 30; len++) {
cnt[len] = cnt[len - 1] + cnt[len - 2];
}
return f(cnt, n, 30);
}
// cnt[len] : 二进制如果有len位，所有二进制状态中不存在连续的1的状态有多少个，辅助数组
// 从num二进制形式的高位开始，当前来到第i位，之前的位完全和num一样
// 返回<=num且不存在连续的1的状态有多少个
public static int f(int[] cnt, int num, int i) {
if (i == -1) {
return 1; // num自身合法
}
int ans = 0;
if ((num & (1 << i)) != 0) {
ans += cnt[i];
if ((num & (1 << (i + 1))) != 0) {
// 如果num二进制状态，前一位是1，当前位也是1
// 如果前缀保持和num一样，后续一定不合法了
// 所以提前返回
return ans;
}
}
// 之前的高位和num一样，且合法，继续去i-1位递归
ans += f(cnt, num, i - 1);
return ans;
}
// 只是把方法1从递归改成迭代而已
// 完全是等义改写，没有新东西
public static int findIntegers2(int n) {
int[] cnt = new int[31];
cnt[0] = 1;
cnt[1] = 2;
for (int len = 2; len <= 30; len++) {
cnt[len] = cnt[len - 1] + cnt[len - 2];
}
int ans = 0;
for (int i = 30; i >= -1; i--) {
if (i == -1) {
ans++;
break;
}
if ((n & (1 << i)) != 0) {
ans += cnt[i];
if ((n & (1 << (i + 1))) != 0) {
break;
}
}
}
return ans;
}
}
code4 1067. 范围内的数字计数
// 范围内的数字计数
// 给定两个正整数a和b，求在[a,b]范围上的所有整数中
// 1 <= a, b
// 某个数码d出现了多少次
// 测试链接 : https://leetcode.cn/problems/digit-count-in-range/
统计每个位上的计数
package class085;
// 范围内的数字计数
// 给定两个正整数a和b，求在[a,b]范围上的所有整数中
// 1 <= a, b
// 某个数码d出现了多少次
// 测试链接 : https://leetcode.cn/problems/digit-count-in-range/
public class Code04_DigitCount1 {
public static int digitsCount(int d, int a, int b) {
return count(b, d) - count(a - 1, d);
}
// 统计1~num范围上所有的数中，数码d出现了多少次
// 注意是1~num范围，不是0~num范围
public static int count(int num, int d) {
int ans = 0;
// left : 当前位左边的情况数
// right : 当前位右边的情况数
// 当前位的数字是cur
for (int right = 1, tmp = num, left, cur; tmp != 0; right *= 10, tmp /= 10) {
// 情况1：
// d != 0
// 1 ~ 30583 , d = 5
// cur < d的情况
// 个位cur=3 : 0000~3057 5
// 个位上没有额外加
//
// cur > d的情况
// 十位cur=8 : 000~304 5 0~9
// 十位上额外加 : 305 5 0~9
//
// cur == d的情况
// 百位cur=5 : 00~29 5 00~99
// 百位上额外加 : 30 5 00~83
// ...
// 情况2：
// d == 0
// 1 ~ 30583 d = 0
// cur > d的情况
// 个位cur=3 : 0001~3057 0
// 个位上额外加 : 3058 0
//
// cur > d的情况
// 十位cur=8 : 001~304 0 0~9
// 十位上额外加 : 305 0 0~9
//
// cur > d的情况
// 百位cur=5 : 01~29 0 00~99
// 百位上额外加 : 30 0 00~99
//
// cur == d的情况
// 千位cur=0 : 1~2 0 000~099
// 千位上额外加 : 3 0 000~583
left = tmp / 10;
cur = tmp % 10;
if (d == 0) {
left--;
}
ans += left * right;
if (cur > d) {
ans += right;
} else if (cur == d) {
ans += num % right + 1;
}
}
return ans;
}
}
code4 P2602 [ZJOI2010] 数字计数
// 范围内的数字计数
// 给定两个正整数a和b，求在[a,b]范围上的所有整数中
// 每个数码(digit)各出现了多少次
// 1 <= a, b
// 测试链接 : https://www.luogu.com.cn/problem/P2602
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
package class085;
// 范围内的数字计数
// 给定两个正整数a和b，求在[a,b]范围上的所有整数中
// 每个数码(digit)各出现了多少次
// 1 <= a, b
// 测试链接 : https://www.luogu.com.cn/problem/P2602
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Code04_DigitCount2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
long a = (long) in.nval;
in.nextToken();
long b = (long) in.nval;
for (int i = 0; i < 9; i++) {
out.print(digitsCount(i, a, b) + " ");
}
out.println(digitsCount(9, a, b));
}
out.flush();
out.close();
br.close();
}
public static long digitsCount(int d, long a, long b) {
return count(b, d) - count(a - 1, d);
}
public static long count(long num, int d) {
long ans = 0;
for (long right = 1, tmp = num, left, cur; tmp != 0; right *= 10, tmp /= 10) {
left = tmp / 10;
if (d == 0) {
left--;
}
ans += left * right;
cur = tmp % 10;
if (cur > d) {
ans += right;
} else if (cur == d) {
ans += num % right + 1;
}
}
return ans;
}
}
code4 233. 数字 1 的个数
// 数字1的个数
// 给定一个整数n
// 计算所有小于等于n的非负整数中数字1出现的个数
// 测试链接 : https://leetcode.cn/problems/number-of-digit-one/
package class085;
// 数字1的个数
// 给定一个整数n
// 计算所有小于等于n的非负整数中数字1出现的个数
// 测试链接 : https://leetcode.cn/problems/number-of-digit-one/
public class Code04_DigitCount3 {
public static int countDigitOne(int n) {
return count(n, 1);
}
public static int count(int num, int d) {
int ans = 0;
for (int right = 1, tmp = num, left, cur; tmp != 0; right *= 10, tmp /= 10) {
left = tmp / 10;
cur = tmp % 10;
if (d == 0) {
left--;
}
ans += left * right;
if (cur > d) {
ans += right;
} else if (cur == d) {
ans += num % right + 1;
}
}
return ans;
}
}
2023-12-18 15:41:10
