class085 数位dp-下【算法】

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;
  }
}

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;
  }
}

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;
  }
}

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;
  }
}

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;
  }
}

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;
  }
}