中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁 > news >正文

南通網(wǎng)站制作專家比較靠譜的網(wǎng)站

南通網(wǎng)站制作專家,比較靠譜的網(wǎng)站,南陽市網(wǎng)站建設(shè),北京市網(wǎng)絡(luò)推廣競(jìng)價(jià)題目 題目鏈接: 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]中滿…

題目

題目鏈接: 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é)果:
在這里插入圖片描述

http://www.risenshineclean.com/news/55034.html

相關(guān)文章:

  • 網(wǎng)頁設(shè)計(jì)的基礎(chǔ)aso優(yōu)化平臺(tái)有哪些
  • 嵊州市住房和城鄉(xiāng)建設(shè)局網(wǎng)站人民日?qǐng)?bào)今日新聞
  • 淄博論壇網(wǎng)站建設(shè)百度營銷
  • 寧波制作網(wǎng)站公司廣告外鏈購買交易平臺(tái)
  • 高端 網(wǎng)站制作廣告營銷方式有哪幾種
  • 企業(yè)信息系統(tǒng)有哪些百度seo軟件
  • 外貿(mào)網(wǎng)站頁面用什么做最好可以推廣的平臺(tái)
  • 網(wǎng)站開發(fā)問題論文定制型營銷網(wǎng)站建設(shè)
  • 分析網(wǎng)站建設(shè)前期的seo準(zhǔn)備工作網(wǎng)絡(luò)營銷案例100例
  • c web網(wǎng)站開發(fā)權(quán)限windows優(yōu)化大師靠譜嗎
  • 江山建設(shè)工程信息網(wǎng)站網(wǎng)站開發(fā)的基本流程
  • 有哪些設(shè)計(jì)網(wǎng)站佛山百度推廣電話
  • 熾樂清網(wǎng)站建設(shè)廣州seo公司官網(wǎng)
  • 計(jì)算機(jī)專業(yè)吃香嗎怎么優(yōu)化標(biāo)題和關(guān)鍵詞排名
  • 做網(wǎng)站教程和維護(hù)網(wǎng)站seo公司 彼億營銷
  • wordpress收藏本站代碼泰安網(wǎng)站推廣優(yōu)化
  • 網(wǎng)站二維碼彈窗推廣優(yōu)化網(wǎng)站排名教程
  • 西安網(wǎng)站建設(shè)首選那家2345電腦版網(wǎng)址導(dǎo)航
  • 做游戲直播那個(gè)網(wǎng)站互聯(lián)網(wǎng)精準(zhǔn)營銷
  • 公司網(wǎng)站怎么發(fā)布文章下載百度安裝
  • dreamweaver做網(wǎng)站學(xué)習(xí)解析做百度推廣員賺錢嗎
  • 做啥網(wǎng)站最掙錢網(wǎng)站按天扣費(fèi)優(yōu)化推廣
  • 網(wǎng)站訂單模板aso優(yōu)化工具
  • 騰訊郵箱網(wǎng)頁版湖南seo網(wǎng)站多少錢
  • 免費(fèi) 建網(wǎng)站seo英文怎么讀
  • 寶安中心醫(yī)院是什么級(jí)別對(duì)seo的理解
  • 校園無線網(wǎng)絡(luò)設(shè)計(jì)方案seo小白入門教學(xué)
  • 網(wǎng)站開發(fā)人員的水平滕州今日頭條新聞
  • wordpress 插件 文本合肥seo網(wǎng)站排名
  • 陽谷網(wǎng)站建設(shè)價(jià)格淘寶關(guān)鍵詞優(yōu)化軟件