題目

題目鏈接： https://www.luogu.com.cn/problem/P4124

分析

給定兩個(gè)長(zhǎng)度為11位的數(shù)字，代表兩個(gè)區(qū)間 [L,R] 需要編寫程序來計(jì)算出，這兩個(gè)區(qū)間內(nèi)滿足要求的數(shù)字個(gè)數(shù)。這樣的題一般來說就是數(shù)位dp題。首先我們可以根據(jù)容斥原理 [0,R]中滿足要求的個(gè)數(shù) - [0,L-1]中滿足要求的個(gè)數(shù) 來計(jì)算出 [L,R] 這個(gè)區(qū)間中滿足要求數(shù)字的數(shù)量。

但是由于給定的數(shù)字范圍很大，超過了int與long類型的范圍，只能用字符串存儲(chǔ)，那么字符串的加減計(jì)算就變得很麻煩了。那么可以這樣計(jì)算 [0,R]-[0,L] 最后再特判一下 L 串是否符合要求，符合要求的話，最后的答案再+1。

根據(jù)題目要求，我們需要使用兩個(gè)變量來記錄前兩個(gè)位置上的數(shù)，用來判斷是否符合條件，還需要一個(gè)變量來記錄當(dāng)前數(shù)字是否滿足要求，還有使用一個(gè)變量來記錄當(dāng)前數(shù)字是否出現(xiàn)過4與8。

然后就是套用數(shù)位dp的模板了。

code

package dp.數(shù)位dp;import java.util.*;public class Main {static final int N = 12;static final int M = (1 << 11);static long[][][][][] memo = new long[N][N][N][2][M];public static void main(String[] args) {Scanner in = new Scanner(System.in);// 由于數(shù)字位數(shù)太大，那么只能用字符串讀取再轉(zhuǎn)成字符數(shù)組char[] l = in.next().toCharArray();char[] r = in.next().toCharArray();reset(r.length);long ans = dfs(r, 0, 10, 10, false, true, 0);reset(l.length);ans -= dfs(l, 0, 10, 10, false, true, 0);if (check(l)) {++ans;}System.out.println(ans);}/**   chs ；從高到底存儲(chǔ)著數(shù)字的每一個(gè)數(shù)位*   i   ：當(dāng)前數(shù)位下標(biāo)*   pp  ：表示當(dāng)前數(shù)位前一位的前一位數(shù)字*   p   ：表示當(dāng)前數(shù)位前一位的數(shù)字*   flag    ：表示當(dāng)前數(shù)字中是否出現(xiàn)過3個(gè)相鄰且相等的數(shù)字*   isLimit ：表示構(gòu)造當(dāng)前位數(shù)字是否受限制*   status  ：用二進(jìn)制位來判斷當(dāng)前數(shù)字中是否同時(shí)出現(xiàn)過4與8* */public static long dfs(char[] chs, int i, int pp, int p, boolean flag, boolean isLimit, int status) {if (i >= chs.length) {return flag ? 1 : 0;}if (!isLimit && memo[i][pp][p][flag ? 1 : 0][status] != -1) {return memo[i][pp][p][flag ? 1 : 0][status];}long ans = 0;int up = isLimit ? chs[i] - '0' : 9;    // 獲取構(gòu)造當(dāng)前數(shù)字的上限// 無前導(dǎo)零for (int d = (i == 0) ? 1 : 0; d <= up; ++d) {// 不能同時(shí)出現(xiàn)4或8if ((d == 4 && ((status >> 8) & 1) != 0) || (d == 8 && ((status >> 4) & 1) != 0)) {continue;}ans += dfs(chs, i + 1, p, d, flag || (pp == p && d == p), isLimit && d == up, status | (1 << d));}if (!isLimit) {memo[i][pp][p][flag ? 1 : 0][status] = ans;}return ans;}// 判斷一個(gè)數(shù)字是否符合條件public static boolean check(char[] chs) {if(chs[0] == '0') { return false; }char pp = 'x', p = 'x';boolean flag=false,cnt4 = false, cnt8 = false;for (char ch : chs) {if (ch == '4') {cnt4 = true;} else if (ch == '8') {cnt8 = true;}if (cnt4 && cnt8) {return false;}if (pp == p && p == ch) {flag=true;}pp = p;p = ch;}return !(cnt4 && cnt8) && flag;}public static void reset(int n) {for (int i = 0; i < n; i++) {for (int j = 0; j < memo[i].length; j++) {for (int k = 0; k < memo[i][j].length; k++) {for (int u = 0; u < memo[i][j][k].length; u++) {Arrays.fill(memo[i][j][k][u], -1);}}}}}
}

提交結(jié)果：