2018年全国多校算法寒假训练营练习比赛（第二场） G 送分了QAQ 【打表 + find】

题目描述

杭州人称傻乎乎的人为62，而嘟嘟家这里没有这样的习俗。

相比62，他那里的人更加讨厌数字38，当然啦，还有4这个

数字！所以啊，嘟嘟不点都不想见到包含38或者4的数字。

每次给出一个区间[n，m],你能找到所有令人讨厌的数字吗？

输入描述:

多组输入输出；
输入的都是整数对n、m（0

输出描述:

对于每次的输入
输出全部令人讨厌的数的个数

示例1

输入

1 100
0 0

输出

20

题意： 略

分析： 本来是数位dp的题，因为范围很小，我们偷懒下，直接打表即可，利用string.find();函数即可，维护一个前缀和，O(1)查询

参考代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 10;

bool check(int x) {
string s;
while (x) {
        s = char(x % 10 + '0') + s;
        x /= 10;
    }
if(s.find("38") != s.npos) return true;
if(s.find("4") != s.npos) return true;
return false;
}

int a[maxn];

void init() {
for(int i = 1;i <= 1000000;i++) {
        a[i] = a[i - 1] + check(i);
    }
}

int main(){
  ios_base::sync_with_stdio(0);
    init();
int n,m;
while(cin>>n>>m,n + m) {
cout<<a[m] - a[n - 1]<<endl;
    }
return 0;
}

• 如有错误或遗漏，请私聊下UP，thx