不要62
Problem Description
杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。
Input
输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。
Output
对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。
Sample Input
1 100
0 0
Sample Output
80
Author
qianneng
Source
题目类型：数位DP
算法分析：dp[i][0]表示长度为i不含不吉利数字的个数，dp[i][1]表示长度为i不含不吉利数字且高位为2的个数，dp[i][2]表示长度为i含有不吉利数字的个数。状态转移方程为dp[i][0] = dp[i-1][0] * 9 - dp[i-1][1]; dp[i][1] = dp[i-1][2]; dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1] + dp[i-1][0]，初始条件为dp[0][0] = 1，最后对于每个读入的数字从高位开始计算：先加上当前位乘上低位含有不吉利数字的个数。然后判断此时不吉利数字是否曾经出现过，若出现过，则累加当前位乘上低位不含有不吉利数字的个数。若此时没有出现过，且最高位的值大于6，则还要加上低位不含有不吉利数字且最高位为2的数字个数，且最高位的值大于4的话，则还要加上低位不含有不吉利数字的个数。最后再判断当前位和高一位的值是否能够组成62或者是4，若可以，则把标志置为true，注意此时还应该判断是否会出现高位为6，而低位比2大的情况，若出现，则还要加上dp[i][1]！！！注意上面求解的是(0, n)范围内满足条件的个数！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
/************************************************* Author :supermaker Created Time :2015/12/1 0:04:06 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; LL dp[26][3], bit[66]; void PP () { memset (dp, 0, sizeof (dp)); dp[0][0] = 1; for (int i = 1; i < 26; i++) { dp[i][0] = dp[i-1][0] * 9 - dp[i-1][1]; dp[i][1] = dp[i-1][0]; dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1] + dp[i-1][0]; } } LL SS (LL n) { int len = 0; LL tt = n; while (n) { bit[++len] = n % 10; n /= 10; } bit[len+1] = 0; LL res = 0; bool is_have = false; for (int i = len; i >= 1; i--) { res += dp[i-1][2] * bit[i]; if (is_have) res += dp[i-1][0] * bit[i]; if (!is_have && bit[i] > 6) res += dp[i-1][1]; if (!is_have && bit[i] > 4) res += dp[i-1][0]; if (!is_have && bit[i+1] == 6 && bit[i] > 2) res += dp[i][1]; if ((bit[i+1] == 6 && bit[i] == 2) || bit[i] == 4) is_have = true; } return tt - res; } int main() { PP (); //CFF; //CPPFF; LL n, m; while (scanf ("%I64d%I64d", &n, &m) != EOF) { if (n == 0 && m == 0) break; LL vala = SS (n); LL valb = SS (m + 1); printf ("%I64d\n", valb - vala); } return 0; } |
算法分析：另一种方法就是dp[i][j]表示开头为j的i位数不是不吉利数的个数，则状态转移方程为dp[i][j] += dp[i-1][k]，其中满足j != 4 && !(j == 6 && k == 2)。最后对于每个输入的n从高位开始计算：若满足不是吉利数的条件，则累加答案。若中间遇到一个不满足条件的数的话，直接break即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
/************************************************* Author :supermaker Created Time :2015/12/1 1:39:44 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; int dp[66][66], bit[66]; void PP () { memset (dp, 0, sizeof (dp)); dp[0][0] = 1; for (int i = 1; i <= 8; i++) for (int j = 0; j < 10; j++) for (int k = 0; k < 10; k++) if (j != 4 && ! (j == 6 && k == 2)) dp[i][j] += dp[i-1][k]; } int SS (int n) { int len = 0; while (n) { bit[++len] = n % 10; n /= 10; } bit[len+1] = 0; int res = 0; for (int i = len; i >= 1; i--) { for (int j = 0; j < bit[i]; j++) { if (j != 4 && !(bit[i+1] == 6 && j == 2)) res += dp[i][j]; } if (bit[i] == 4 || (bit[i+1] == 6 && bit[i] == 2)) break; } return res; } int main() { //CFF; //CPPFF; PP (); int n, m; while (scanf ("%d%d", &n, &m) != EOF) { if (n == 0 && m == 0) break; printf ("%d\n", SS (m + 1) - SS (n)); } return 0; } |
- « 上一篇：hdu3555
- poj3186：下一篇 »