題解 :

首先能夠發現幸運數的取值總共有1023種, 位數分別是1…10
位數為10的只有4444444444.
其余可以按照二進制排列組合（4, 7當成0，1看）構成幸運數
共有∑i=192i=210?2=1022

記第i個幸運數為a[i], 那么幸運數位a[i]的數范圍為(a[i - 1], a[i]]

預處理所有的幸運數

然后查找l, r在幸運數數組種中完全包含的區間， 直接處理：
[l, r]包含某個區間(a[i - 1], a[i]]此區間內所有數字幸運數之和為
a[i] * (a[i] - a[i - 1])然后處理兩端的區間.

怎么處理幸運數呢， 注意到幸運數遞增的， 且a[i]是第一個比a[i - 1]大的幸運數， 用串模擬下就可

code:

/***Author : adrui*Language : C++*Created at 2017/03/27* **/#include <iostream> #include <map> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; typedef long long ll;const int N = 1024; ll a[N]; string toString(ll x){string s = "";while(x){s += x % 10 + '0';x /= 10;}return s; } ll ch(string s){/**轉整數*///cout << s << endl;ll res = 0;for(int i = s.length() - 1; i >= 0; --i)res = 10 * res + s[i] - '0';return res; } ll cal(ll x){string s = toString(x);/**逆向串*///cout << s << endl;int f = 0, len = s.length();for(int i = 0; i < len - 1; ++i){if(s[i] < '7') {s[i] = '7', f = 1;break;}else s[i] = '4', ++s[i + 1];}if(!f)if(s[len - 1] < '7') s[len - 1] = '7';else {s[len - 1] = '4'; return ch(s + "4");}return ch(s); }void init(){/**預處理幸運數*/a[0] = 0;a[1] = 4;a[2] = 7;for(int i = 3; i < N; ++i){//cout <<a[i-1] << endl;a[i] = cal(a[i - 1]);/**求a[i]， 沒打表意識。*///cout << ":"<<a[i] << endl;// cout << a[i] << endl;} }ll solve(ll l, ll r){ll res = 0, i;int pos1 = lower_bound(a, a + N, l) - a, pos2 = lower_bound(a, a + N, r) - a - 1;/**二分找l, r *///cout << pos1 << " " << pos2 << endl;if(pos1 <= pos2)/**l, r不在一個區間*/for(i = pos1 + 1; i <= pos2; ++i){/**處理中間*/res += (a[i] - a[i - 1]) * a[i];}res += (a[pos1] - l + 1) * a[pos1];/**兩端*/res += (r - a[pos2]) * a[pos2 + 1];}else{/**l, r在同一個區間*/res += (r - l + 1) * a[pos2 + 1];}return res; } int main(){//freopen("in.txt", "r", stdin);init();int t;cin >> t;ll l, r;while(t--){cin >> l >> r;cout << solve(l, r) << endl;}return 0; }

總結

以上是生活随笔為你收集整理的AHU-2017校赛现场赛 B 下一个幸运数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。