HDU 2089 不要62 【数位DP】_综合

Problem Description

杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。

Input

输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。

Output

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

Sample Input

Sample Output

#include <stdio.h>//TLE
int main()
{//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);int n, m;while (~scanf("%d%d", &n, &m) && n) {int sum = 0;for (int i = n;i <= m;i++) {int t = i, flag1 = 0, flag2 = 0;while (t) {//判断是否含‘62’if (t % 100 == 62) {sum++;flag1 = 1;break;}t /= 100;}t = i;while (t) {//判断是否含4if (t % 10 == 4) {sum++;flag2 = 1;break;}t /= 10;}if (flag1&&flag2) sum--;//都含}printf("%d\n",m-n+1-sum);}return 0;
}

#include <stdio.h>//又TLE了！
#include <string.h>
#define maxn 1000010
char buf[maxn];
int main()
{//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);int n, m;while (~scanf("%d%d", &n, &m) && n) {int sum = 0;for (int i = n;i <= m;i++) {int flag1 = 0, flag2 = 0;sprintf(buf, "%d", i);if (strchr(buf, '4') != NULL) {//查4sum++;flag1 = 1;}if (strstr(buf, "62") != NULL) {//查62sum++;flag2 = 1;}if (flag1&&flag2) sum--;//都含}printf("%d\n", m - n + 1 - sum);}return 0;
}

以上两种版本稍稍改进下，进行预处理，发现光是预处理就TLE了！甚至自己的机器上都得不到结果！因为预处理用时太长，还没跑完！

#include <stdio.h>
#include <string.h>
#define maxn 1000010
int sum[maxn], ans[maxn];
int main()
{memset(ans, 0, sizeof(ans));//ans[i]表示在<=i区间内正常数字个数memset(sum, 0, sizeof(sum));//sum[i]表示在<=i区间内不吉利数字个数for (int i = 1;i < maxn;i++) {for (int j = 1;j <= i;j++){int t = j;while (t) {if (t % 100 == 62 || t % 10 == 4) {sum[i]++;break;}t /= 10;}}ans[i] = i - sum[i];}//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);int n, m;while (~scanf("%d%d", &n, &m) &&(n||m)) {printf("%d\n",ans[m]-ans[n-1]);}return 0;
}

#include <stdio.h>
#include <string.h>
#define maxn 1000010
char buf[maxn];
int sum[maxn], ans[maxn];
int main()
{memset(ans, 0, sizeof(ans));//ans[i]表示在<=i区间内正常数字个数memset(sum, 0, sizeof(sum));//sum[i]表示在<=i区间内不吉利数字个数for (int i = 1;i < maxn;i++){for (int j = 1;j <= i;j++){sprintf(buf, "%d", j);if (strchr(buf, '4') != NULL || strstr(buf, "62") != NULL)sum[i]++;}ans[i] = i - sum[i];}//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);int n, m;while (~scanf("%d%d", &n, &m) && n) {printf("%d\n", ans[m] - ans[n - 1]);}return 0;
}

网搜数位DP，思路如下。 初探数位DP

基础知识：

[l,r] 意为 l<=且<=r的数；[l,r) 意为 l<=且< r的数；(l,r] 意为 l< 且<=r的数；(l,r) 意为 l< 且< r的数

方括号意味着取等，小括号意味着不取等

基本思想和方法：

OI中经常需要统计区间[l,r]的满足题意的数的个数，这往往可以转换成求[0,r]-[0,l)

对于求区间[0,n)有一个通用的方法。对于一个小于n的数，肯定是从高位到低位出现某一位<n的那一位。

如 n = 58 n为十进制数。x =49 此时x的十位<n。x =51 此时x的个位<n。

有了上述性质，我们就可以从高到低枚举第一次<n对应位是哪一位。这样之前的位确定了，之后的位就不受n的限制即从00...0~99...9，可以先预处理，然后这时就可以直接统计答案。

说明：

预处理f数组。

F[i,st] 代表位数为i（可能允许前导0。如00058也是个5位数），状态为st的方案数。这里st根据题目需要确定。

如i=4,f[i,st]也就是0000~9999的符合条件的数的个数（十进制）

决策第i位是多少(such as 0~9)

F[i,st] = F[i,st] + f[i–1,st']，st'为相对应的状态。

参照刚刚所说的基本思路。预处理f数组，然后统计[0,m]- [0,n)。f[i,j]代表开头是j的i位数中不含"62"或"4"的数有几个。

如f[2,6]包含60,61,63,65,66,67,68,69

for(int i=1;i<=7;i++){for(int j=0;j<10;j++)//枚举第i位可能出现的数{for(int k=0;k<10;k++)//枚举第i-1位可能出现的数{if(j!=4&&!(j==6&&k==2))dp[i][j]  += dp[i-1][k];}}}

#include <stdio.h>
#include <string.h>
int dp[8][10];//dp[i][j]表示第i位是数字j时符合条件的数字个数
int digit[9];//digit[i]表示n从右到左第i位的数字
int i, j, k;
void init()//预处理
{memset(dp, 0, sizeof(dp));dp[0][0] = 1;//dp[1][1]表示只有一位，并且以1开头的数，那么就是1,1是符合条件的，//故dp[1][1]=1,而dp[1][1] = sum(dp[0][k])0<=k<=9,故dp[0][k]里面肯定要有一个为1的，//而这个1不一定要是dp[0][0],设dp[0][1] = 1也是可以的，只要保证0位的时候有一个为1就行//此处精辟解释参见http://blog.csdn.net/wangyuquanliuli/article/details/13761661处评论for (i = 1;i <= 7;i++)//0<n≤m<1000000{for (j = 0;j < 10;j++)//j是第i位数字{for (k = 0;k < 10;k++)//k是第i-1位数字{//dpi[i][j]=sum(dp[i-1][k])且!(j == 6 && k == 2) && j != 4,其中k取值[0,9]if (!(j == 6 && k == 2) && j != 4)dp[i][j] += dp[i - 1][k];}}}
}
int calclen(int n)//计算n的长度
{int tmp = 0;while (n) {tmp++;n /= 10;}return tmp;
}
void calcdigit(int n,int len)//计算n的digit数组
{memset(digit, 0, sizeof(digit));//digit[i]表示n从右到左第i位的数字for (i = 1;i <= len;i++){digit[i] = n % 10;n /= 10;}
}
int solve(int n)//计算区间[0,n)内的正常数个数
{int ans = 0;int len = calclen(n);calcdigit(n,len);for (int i = len;i >= 1;i--)//从高位开始枚举，digit[len]是最高位{for (int j = 0;j < digit[i];j++)//枚举第i位取值情况{//注意！这里j不取到digit[i]，因为ans就是dp[i][digit[i]],取digit[i]就重复计算了！if (!(j == 2 && digit[i + 1] == 6) && j != 4)//第i位是j时符合条件ans += dp[i][j];}if (digit[i] == 4 || (digit[i] == 2 && digit[i + 1] == 6)) break;//第i位已经不满足条件了，则i位以后就不可能满足条件，跳出循环	}return ans;
}
int main()
{//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);init();int l, r;while (~scanf("%d%d", &l, &r) && (l || r)) {printf("%d\n", solve(r+1) - solve(l));//solve(n)计算的是[0,n)区间的，而[0,m+1)-[0,n)=[n,m+1)=[n,m]}
}