CF535B Tavas and SaDDas

Buried_Dream · 2022-04-10 11:02:06 · 题解

很明显吧，这题是分块打表的板子题。

分块打表很快啊，快如闪电，啪一下就切了。

这题连块长都不用卡，简直是分块打表的模板。

题意：

幸运数字的定义：每一位只含有 4 或 7。

找到从 1 到 n 内幸运数字的个数。

思路：

分块打表，数据范围是 1e9，块长就设 1e5 足够了。

写个判断函数开始打表就行了。

给出打表代码：

bool Check(int x) {
    while(x) {
        if(x % 10 != 4 && x % 10 != 7) return false;
        x /= 10; 
    }return true;
}

int Bel = 1e5;

int cnt = 0;

signed main() {
    for(int i = 1; i <= 1e9; i++)  {
        if(Check(i)) cnt++;
        if(i % Bel == 0) printf("%lld,", cnt), cnt = 0;
    }
}

查询答案的时候，整块直接加，散块暴力求。

代码在剪切板里：https://www.luogu.com.cn/paste/x19xe57n