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

时间:2021-11-16 11:48:56

题目描述

杭州人称傻乎乎的人为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