第六周

2. 求和

第一种思路

预处理所有满足要求的数。

然后用快速求区间交的方法算答案。

即，设 a 为区间左端点, b 为区间右端点，x 为查询区间左端点， y 为查询区间右端点。

当 x <= a <= b <= y 时 [a, b] 与 [x, y] 的交是 [a, b]
当 a <= x <= b <= y 时 [a, b] 与 [x, y] 的交是 [x, b]
当 a <= x <= y <= b 时 [a, b] 与 [x, y] 的交是 [x, y]
当 x <= a <= y <= b 时 [a, b] 与 [x, y] 的交是 [a, y]

所以可以用 max(0ll, (min(r, b) - max(l, a)) + 1); 来算

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;

typedef long long LL;

LL l, r, ans;
vector<LL> S;

void dfs(int u, LL x)
{
    S.push_back(x);
    if (u == 10) return;
    dfs(u + 1, x * 10 + 4);
    dfs(u + 1, x * 10 + 7);
}

int main()
{
    dfs(0, 0);
    sort(S.begin(), S.end());
    scanf("%lld %lld", &l, &r);
    for (int i = 1; i < S.size(); i ++ )
    {
        LL a = S[i - 1] + 1, b = S[i];
        ans += S[i] * max(0ll, (min(r, b) - max(l, a)) + 1);
    }
    printf("%lld", ans);
}

3. 构造完全图

第一种思路

qwq, 考完再写。