AcWing算法周赛第6场 | 3734 求和

学习C++从娃娃抓起！记录下AcWing备赛学习过程中的题目，记录每一个瞬间。

附上汇总贴：AcWing算法周赛 ｜汇总

【题目描述】

用 f ( x ) f(x) f(x) 来表示满足下列条件的最小正整数 a a a：

1. a ≥ x a\ge x a≥x。
2. a a a 的各个数位不包含除了 4 4 4 和 7 7 7 以外的其他数字。

现在，给定两个整数 l , r ( l ≤ r ) l,r(l\le r) l,r(l≤r)，请你计算 f ( l ) + f ( l + 1 ) + . . . + f ( r ) f(l)+f(l+1)+...+f(r) f(l)+f(l+1)+...+f(r) 的值。

【输入】

一行，两个整数 l , r l,r l,r。

【输出】

一行，一个整数表示求得的和。

【输入样例】

2 7

【输出样例】

33

【分析】

【代码详解】

《AcWing 3734 求和》 #DFS# #枚举#

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> s;
void dfs(int u, int x)
{
    s.push_back(x);
    if (u==10) return;
    dfs(u+1, x*10+4);
    dfs(u+1, x*10+7);
}
signed main()
{
    dfs(0, 0);
    sort(s.begin(), s.end());
    int l , r;
    cin >> l >> r;
    int res = 0;
    for (int i=1; i<s.size(); i++)
    {
        int a = s[i-1]+1, b = s[i];
        res += s[i] * max(0ll, (min(r, b)-max(l, a)+1));
    }
    cout << res << endl;
    return 0;
}

【运行结果】

2 7
33