幸运数字Ⅱ

幸运数字只由4和7组成 一开始想要去打表 感觉也没问题 每次二分查找 更新边界就可以了
因为数字是由4和7组成 很容易发现规律
4 7 44 47 74 77 444 447很像队列 每次用队首拓展出两个新元素 规律如下

ll tmp1 = q.front() * 10 + 4, tmp2 = q.front() * 10 + 7;
q.pop();
q.push(tmp1);
q.push(tmp2);

那么后面就很简单了 每次更新范围 判断l，r和tmp1，tmp2的大小关系 一共只有六种：

1. l > tmp2;(这个需要先判断 不然会导致错误 因为l > tmp2 == l > tmp1)
2. r <= tmp1;
3. l <= tmp1 && r <= tmp2;
4. l <= tmp1 && r > tmp2;
5. l > tmp1 && r <= tmp2;
6. l > tmp1 && r > tmp2;

每次依照这个范围更新答案就可以了 代码如下

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  int l, r;cin >> l >> r;
  ll ans = 0;
  
  auto bfs = [&]() -> void {
    queue<ll> q;
    q.push(0);
    while (q.size()) {
      ll tmp = q.front();
      q.pop();
      ll tmp1 = tmp * 10 + 4;
      ll tmp2 = tmp * 10 + 7;
      q.push(tmp1);
      q.push(tmp2);
      //一共六种情况
      if (l > tmp2) continue;
      else if (r <= tmp1) {
        ans += 1ll * (r - l + 1) * tmp1;
        break;
      }
      else if (l <= tmp1 && r <= tmp2) {
        ans += 1ll * (tmp1 - l + 1) * tmp1 + 1ll * (r - tmp1) * tmp2;
        break;
      }
      else if (l <= tmp1 && r > tmp2) {
        ans += 1ll * (tmp1 - l + 1) * tmp1 + 1ll * (tmp2 - tmp1) * tmp2;
        l = (tmp2 + 1ll);
      }
      else if (l > tmp1 && r <= tmp2) {
        ans += 1ll * (r - l + 1) * tmp2;
        break;
      }
      else if (l > tmp1 && r > tmp2) {
        ans += 1ll * (tmp2 - l + 1) * tmp2;
        l = (tmp2 + 1ll);
      }
    }
  };
  bfs();
  cout << ans << '\n';
}