前言The Counting PRoblemRound NumbersFxX mod fx
在前一節鏈接里，我們討論了數位dp的基礎應用，從數位dp的簡單狀態刻畫狀態方程的給出，以及之后給出了較為統一的記憶化模板來解決大多數問題，在這一節里首先給出一個較復雜的狀態方程求解問題，剩下3個用記憶化解決的問題來加深印象。
POJ 2282 題目鏈接 Given two integers a and b, we write the numbers between a and b, inclusive, in a list. Your task is to calculate the number of occurrences of each digit. For example, if a = 1024 and b = 1032, the list will be 1024 1025 1026 1027 1028 1029 1030 1031 1032
there are ten 0’s in the list, ten 1’s, seven 2’s, three 3’s, and etc.
【題目大意】求出給定區間內0~9每個數出現的次數
【題目思路】定義dp[i][j][k]為 以j開頭含有i位數字 其中出現數字k的個數 狀態轉移方程：若j=k，（即第一位數字為出現的數字），
需要注意：
在統計個數時，對出現在前綴上的數字需要加上之后組成的數字個數。第一位取0時要特殊考慮，要減去這次0出現的次數以及后面每次0在首位出現的次數。【程序代碼】
/*求出區間內0~9的個數*/#include<iostream>#include<vector>#include<cstring>using namespace std;int dp[10][10][10]; //dp[i][j][k] 表示以j開頭i位數字 含有數字k的個數 int ans[10][2];int pos = 0;vector<int> v;int work(int n) //求10^n { int s = 1, i; for(i=1; i<=n; i++) { s *= 10; } return s;}int js(int j) //求v[j-1]~v[0]組成的數字 { int s = 0; int i; for(i=j; i>=0; i--) { s = s* 10 + v[i]; } return s;}void solve(int x){ v.clear(); while(x > 0) { v.push_back(x % 10); x /= 10; } int i, j, k; for(i=v.size(); i>0; i--) { for(j=v[i-1]-1; j>=0; j--) { for(k=0; k<=9; k++) { ans[k][pos] += dp[i][j][k]; if(j==0 && i==v.size() && k==0) //第一位數字取0減去這次0在第一位出現的個數 //以及后面每次0在首位的情況。 { int t = work(v.size()-1); while(t > 1){ ans[k][pos] -= t; t /= 10; } } } } ans[v[i-1]][pos] += js(i-2); //第i位數字取原數字需要加 后面組成的數字個數 } pos++;}int main(){ int a, b; int i, j, k, kk; for(i=0; i<=9; i++) { dp[1][i][i] = 1; } for(i=2; i<=9; i++) { for(j=0; j<=9; j++) { for(k=0; k<=9; k++) { if(j==k){ dp[i][j][k] = work(i-1); } for(kk=0; kk<=9; kk++) { dp[i][j][k] += dp[i-1][kk][k]; } } } } while(1) { cin >> a >> b; pos = 0; memset(ans, 0, sizeof(ans)); if(a == 0 && b == 0){ break; } if(a > b){ int t = a; a = b; b = t; } solve(b+1); solve(a); for(i=0; i<=9; i++) { cout << ans[i][0] - ans[i][1] << " "; } cout << endl; } return 0;}POJ3252 題目鏈接 The cows, as you know, have no fingers or thumbs and thus are unable to play Scissors, Paper, Stone’ (also known as ‘Rock, Paper, Scissors’, ‘Ro, Sham, Bo’, and a host of other names) in order to make arbitrary decisions such as who gets to be milked first. They can’t even flip a coin because it’s so hard to toss using hooves.
They have thus resorted to “round number” matching. The first cow picks an integer less than two billion. The second cow does the same. If the numbers are both “round numbers”, the first cow wins, otherwise the second cow wins.
A positive integer N is said to be a “round number” if the binary representation of N has as many or more zeroes than it has ones. For example, the integer 9, when written in binary form, is 1001. 1001 has two zeroes and two ones; thus, 9 is a round number. The integer 26 is 11010 in binary; since it has two zeroes and three ones, it is not a round number.
Obviously, it takes cows a while to convert numbers to binary, so the winner takes a while to determine. Bessie wants to cheat and thinks she can do that if she knows how many “round numbers” are in a given range.
Help her by writing a program that tells how many round numbers appear in the inclusive range given by the input (1 ≤ Start < Finish ≤ 2,000,000,000).
【題目大意】統計給定區間內 數字的二進制表示中0個數大于1個數，這樣符合條件的數據有多少。
【題目思路】運用記憶化搜索，定義dp[i][j][k] 處理i位置 j代表(0個數-1個數) k=1表示之前有填過1 為了防止j出現負數，將j累加40（初始傳遞值為40，以40定義標準1個數等同0個數），dfs中用has記錄是否之前有1，若沒有，則不記錄這次01個數差，因為數字不能出現前導0。
【程序代碼】
#include<iostream>#include<vector>#include<stdio.h>#include<cstring>using namespace std;int dp[50][80][2]; //dp[i][j][k]處理i位置 j代表0個數-1個數 k=1表示之前有填過1 vector<int> v;int dfs(int pos, int s, int has, bool limit){ if(pos == 0){ return s >= 40&&has; } if(!limit && dp[pos][s][has] != -1) { return dp[pos][s][has]; } int i; int num = limit? v[pos-1]: 1; int ans = 0; for(i=0; i<=num; i++) { if(has){ if(i==0){ ans += dfs(pos-1, s+1, 1, limit&&i==num); } else{ ans += dfs(pos-1, s-1, 1, limit&&i==num); } } else{ if(i==1){ ans += dfs(pos-1, s-1, 1, limit&&i==num); } else{ ans += dfs(pos-1, s, has, limit&&i==num); } } } if(!limit){ dp[pos][s][has] = ans; } return ans;}int solve(int x){ v.clear(); while(x > 0){ v.push_back(x % 2); x /= 2; } return dfs(v.size(), 40, 0, true);}int main(){ int x, y; //freopen("tt", "r", stdin); //freopen("a", "w", stdout); memset(dp, -1, sizeof(dp)); while(~scanf("%d%d",&x,&y)) printf("%d/n",solve(y)-solve(x-1)); return 0; }hdu4734 題目鏈接 For a decimal number x with n digits (AnAn-1An-2 … A2A1), we define its weight as F(x) = An * 2n-1 + An-1 * 2n-2 + … + A2 * 2 + A1 * 1. Now you are given two numbers A and B, please calculate how many numbers are there between 0 and B, inclusive, whose weight is no more than F(A).
【題目大意】 F(x) = An * 2n-1 + An-1 * 2n-2 + … + A2 * 2 + A1 * 1，給出A，B，求出[0, B]中x個數，滿足F(x) < F(A)
【題目思路】 記憶化。 A范圍[0, 10^9]，F(A)范圍[0, 9*2^9]，調用dfs時權值和賦值F(A) 定義dp[i][j] 表示正在處理第i位，權值和剩下j時的方法總數，若最終處理0位時，權值和小于0，表示此種填充方式可行。 剩下的套記憶化的模板即可
【程序代碼】
#include<iostream>#include<stdio.h>#include<vector>#include<cstring>using namespace std;int dp[11][15000];vector<int> v;int work(int n) //求2^n{ int s = 1; for(int i=1; i<=n; i++) { s *= 2; } return s;}int dfs(int pos, int w, bool limit){ if(pos == 0){ return 1; } if(!limit && dp[pos][w] != -1){ return dp[pos][w]; } int num = limit? v[pos-1]: 9; int i; int ans = 0; for(i=0; i<=num; i++) { int h = i * work(pos-1); if(h <= w) { ans += dfs(pos-1, w-h, limit&&i==num); } } if(!limit){ dp[pos][w] = ans; } return ans;}int solve(int A, int B){ v.clear(); while(B > 0){ v.push_back(B % 10); B /= 10; } int i = 1; int s = 0; //求F(A) while(A > 0) { int t = A % 10; s += t * i; i *= 2; A /= 10; } return dfs(v.size(), s, true);}int main(){ int t; int i, j, k; cin >> t; memset(dp, -1, sizeof(dp)); for(i=1; i<=t; i++) { int A, B; scanf("%d%d", &A, &B); int ans = solve(A, B); printf("Case #%d: %d/n", i, ans); } return 0;}hdu4389 題目鏈接 Here is a function f(x): int f ( int x ) { if ( x == 0 ) return 0; return f ( x / 10 ) + x % 10; }
Now, you want to know, in a given interval [A, B] (1 <= A <= B <= 109), how many integer x that mod f(x) equal to 0.
【題目大意】 求給定區間內 數字x % x各位上數字和=0，這樣的x有多少個。
【題目思路】 前一節有一道題是%13的問題，這次是% x各位上數字和，x各位上數字和最大為9*9=81，這次通過枚舉1~81來調用dfs 定義dp[i][j][k][m] 還剩i位數 前面的數字和為j 目前組成的數與m相余為k 的方法數，剩下的套模板和hdu3652 差不多。
【程序代碼】
#include<iostream>#include<stdio.h>#include<vector>#include<cstring>using namespace std;vector<int> v;int dp[11][82][82][82];//dp[i][j][k][m] : 還剩i位數 前面的數字和為j 目前組成的數與m相余為k int dfs(int pos, int sum, int modv, int mod, bool limit){ if(pos == 0){ if(sum == mod && modv == 0){ return 1; } return 0; } if(!limit && dp[pos][sum][modv][mod] != -1) { return dp[pos][sum][modv][mod]; } int num = limit? v[pos-1]:9; int i, j; int ans = 0; for(i=0; i<=num; i++) { ans += dfs(pos-1, sum+i, (modv*10+i) % mod, mod, limit&&i==num); } if(!limit){ dp[pos][sum][modv][mod] = ans; } return ans;}int solve(int x){ v.clear(); while(x > 0) { v.push_back(x % 10); x /= 10; } int ans = 0; int i; for(i=1; i<=81; i++) { ans += dfs(v.size(), 0, 0, i, true); } return ans;} int main(){ int t;// freopen("tt", "r", stdin);// freopen("a", "w", stdout); int i, j, k; cin >> t; memset(dp, -1, sizeof(dp)); for(i=1; i<=t; i++) { int x, y; cin >> x >> y; printf("Case %d: %d/n", i, solve(y) - solve(x-1)); } return 0;}新聞熱點
疑難解答
