HDU 2089 不要62：
题目大意是给你一个区间，让你统计这个区间里不包含 4 和 62 的数字的个数。
最朴素的思路是：
对于每个区间 [l, r]，遍历所有在区间 [l, r] 里的数字，然后检查每个数字是不是合法（没有 4 和 62 ），如果合法答案加一。
代码如下：
#include<bits/stdc++.h>
using namespace std;
bool check(int a) {
while (a) {
int b = a % 10;
int c = a % 100;
if (b == 4 || c == 62)
return false;
a /= 10;
}
return true;
}
int main() {
int n, m;
while (cin >> n >> m) {
int sum = 0;
if (n == 0 && m == 0)
return 0;
for (int i = n; i <= m; i++) {
if (check(i))
sum++;
}
cout << sum << endl;
}
return 0;
}
对于本题，上面的代码是可以通过的（ 998ms 险过），本题时限 1000ms，时间复杂度是非常高的。
引入数位的概念（个位、十位、百位 ... ），有了数位，就可以换一种方式遍历数字，即：
比如对于 [1, 234] 这个区间，就可以按数位去遍历。
遍历百位数，如果百位数小于这一位的最大值 2 ，那么它的的下一位的最大值为 9 ，否则它的下一位最大值就为 3。以此类推，遍历十位数，如果十位数小于 3，那么它的下一位最大值为 9，否则为 4。
对于这种遍历数字的方法，当区间最小值为 1 的时候是容易的，但如果最小值大于 1，遍历的时候不但要考虑数位的最大值，还要考虑数位的最小值，遍历起来会麻烦许多，因此，可以利用前缀和的思想，求 F(n - 1) = { 1 - ( n - 1 ) 的数字数 } 和 F(m) = { 1 - m 的数字数 }，然后 ANS = F(m) - F(n - 1)。
那样就可以根据上面的思路写出 统计一个区间里数字个数 的遍历数位式的代码：
统计区间里数字个数（错误）：
#include <bits/stdc++.h>
using namespace std;
int a[1005];
int cnt(int po, int lim)
//po表示当前遍历到第几个数位，lim表示本次遍历有没有最大值限制
{
if(po == -1)return 1;
//如果遍历到最后一位了，返回 1，表示加了一个数字。
int len = lim ? a[po] : 9, i, ans = 0;
//如果有数位最大值限制，那 len 就是最大值，否则数字可以遍历到 9。
for(i = 0; i <= len; i++)
{
ans += cnt(po - 1, i == len ? 1 : 0);
//遍历下一位，加到ans里，如果 i 遍历到了最大值，那么下一位将受到限制。
}
return ans;
返回答案。
}
int num(int n)
{
int p = 0, i;
while(n)
{
a[p++] = n % 10;
n /= 10;
}
//将数字拆分
int ans = cnt(p - 1, 1);
return ans;
}
int main()
{
int n, m;
while(scanf(\"%d %d\", &n, &m) != EOF)
{
int ans = num(m) - num(n - 1);
//前缀和求解答案。
printf(\"%d\\n\", ans);
}
return 0;
}
尽管能很容易的按照思路敲出代码，但上面的代码是错误的！原因就是：
如果某一位不受限制，当这一位遍历到 9 时，它的下一位会变成受限制的一位（不应该受限制）。
那么怎么处理呢？
判断下一位是否受限制的时候要判断当前位是否受限，如果当前位受限且遍历到了最大值，下一位才会受限。
统计区间里数字个数（正确）：
#include <bits/stdc++.h>
using namespace std;
int a[1005];
int cnt(int po, int lim)
{
if(po == -1)return 1;
int len = lim ? a[po] : 9, i, ans = 0;
for(i = 0; i <= len; i++)
{
ans += cnt(po - 1, i == len && lim);
}
return ans;
}
int num(int n)
{
int p = 0, i;
while(n)
{
a[p++] = n % 10;
n /= 10;
}
int ans = cnt(p - 1, 1);
}
int main()
{
int n, m;
while(scanf(\"%d %d\", &n, &m) != EOF)
{
int ans = num(m) - num(n - 1);
printf(\"%d\\n\", ans);
}
return 0;
}
现在，有了一个用数位方法遍历区间内所有数字的代码，接下来就可以用它来解决问题。
先解决简单的，把包含 4 的数字从答案中删去。
只需要遍历的时候判断一下，遍历到四即跳过。
统计区间里不包含 4 的数字个数：
#include <bits/stdc++.h>
using namespace std;
int a[1005];
int cnt(int po, int lim)
{
if(po == -1)return 1;
int len = lim ? a[po] : 9, i, ans = 0;
for(i = 0; i <= len; i++)
{
if(i == 4)continue;
//如果遍历到 4 ，跳过。
ans += cnt(po - 1, i == len ? && lim);
}
return ans;
}
int num(int n)
{
int p = 0, i;
while(n)
{
a[p++] = n % 10;
n /= 10;
}
int ans = cnt(p - 1, 1);
return ans;
}
int main()
{
int n, m;
while(scanf(\"%d %d\", &n, &m) != EOF)
{
int ans = num(m) - num(n - 1);
printf(\"%d\\n\", ans);
}
return 0;
}
做完这些，应该能比较容易的实现 统计一个区间里不包含某个数的数字个数了。
但如果要统计不包含连续的两个数的数字（ 62 ）该怎么统计呢？
每次遍历到 2 的时候就需要回去看一下它的前一位是否为 6，如果为 6，那么这个数字就不合法。
统计区间里不包含4和62的数字个数：
#include <bits/stdc++.h>
using namespace std;
int a[1005];
int cnt(int po, int lim, int la)
//la表示前一位的数值
{
if(po == -1)return 1;
int len = lim ? a[po] : 9, i, ans = 0;
for(i = 0; i <= len; i++)
{
if(i == 4)continue;
if(la == 6 && i == 2){continue;}
//如果前一位为 6 且当前位是 2 ，跳过。
ans += cnt(po - 1, i == len && lim, i);
}
return ans;
}
int num(int n)
{
int p = 0, i;
while(n)
{
a[p++] = n % 10;
n /= 10;
}
int ans = cnt(p - 1, 1, 0);
}
int main()
{
int n, m;
while(scanf(\"%d %d\", &n, &m) != EOF)
{
int ans = num(m) - num(n - 1);
printf(\"%d\\n\", ans);
}
return 0;
}
写到这里，就已经完成了用遍历数位的方法求解这道题目，并且这份代码是可以 AC 的（ 187ms ），时间效率上提高了很多。
HDU 3555 Bomb：
题目大意是统计一个区间里包含49的数字个数。
与上面的题目非常相似，从上一题的思路过渡一下：
可以统计区间里不包含 49 的数字个数，然后用区间里数字总个数减去不包含 49 的数字个数，就是要的答案。
拿过上面的代码，稍作修改，就可以得到本题的代码：
统计区间里包含49的数字个数（TLE）：
#include <bits/stdc++.h>
using namespace std;
int a[1005];
int cnt(int po, int lim, int la)
{
if(po == -1)return 1;
int len = lim ? a[po] : 9, i, ans = 0;
for(i = 0; i <= len; i++)
{
if(la == 4 && i == 9){continue;}
ans += cnt(po - 1, i == len && lim, i);
}
return ans;
}
int num(int n)
{
int p = 0, i;
while(n)
{
a[p++] = n % 10;
n /= 10;
}
int ans = cnt(p - 1, 1, 0);
}
int main()
{
int n, m;
scanf(\"%d\", &m);
while(scanf(\"%d\", &n) != EOF)
{
if(n == 0 && m == 0)break;
int ans = num(n) - num(0);
printf(\"%d\\n\", n - ans);
}
return 0;
}
提交之后发现超时了：
在这份代码中，对于每个数位，其实遍历了不止一次，这样就造成了时间上的浪费，那么可以通过记忆化搜索优化。
统计区间里包含 49 的数字个数（AC）：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1005], dp[1005][2][10] = {0};
ll cnt(ll po, ll lim, ll la)
{
if(po == -1)return 1;
if(dp[po][lim][la])return dp[po][lim][la];
ll len = lim ? a[po] : 9, i, ans = 0;
for(i = 0; i <= len; i++)
{
if(la == 4 && i == 9){continue;}
ans += cnt(po - 1, (i == len) && lim, i);
}
dp[po][lim][la] = ans;
return ans;
}
ll num(ll n)
{
ll p = 0, i;
while(n)
{
a[p++] = n % 10;
n /= 10;
}
memset(dp, 0, sizeof(dp));
ll ans = cnt(p - 1, 1, 0);
return ans;
}
int main()
{
ll n, m;
scanf(\"%lld\", &m);
while(scanf(\"%lld\", &n) != EOF)
{
//if(n == 0 && m == 0)break;
ll ans = num(n) - num(0);
printf(\"%lld\\n\", n - ans);
}
return 0;
}
这样的代码大概就是 数位DP 了。
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
