CF121A Lucky Sum 题解

题面。

不好意思，又双把通过率拉低了。在 CF 上交了 22 次才过。这里给出不同的写法。

思路

规律其他题解写得都很好，这里不需要再讲述如何推出规律。预处理出前 \(5000\) 个符合要求的数（其实我也不知道处理多少个刚好够，就随便写了一个数）。接下来借用到一点分块思想，将整个 \([l,r]\) 区间拆成三个大部分：左边散块，右边散块以及中间的整块。这里要运用二分找出 \(l\)，\(r\) 所在的块 \(L\) 和 \(R\) 中。

对于左右的散块，数学方法 \(O(1)\) 处理。对于中间的整块，显然有 \(R - L\) 个整块，每块进行单独处理即可。

特判

当 \(l\) 与 \(r\) 在同一个块时直接暴力处理。

代码

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cstring>
#include<algorithm>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#define ll long long
#define inf 0x3f3f3f3f
#define fr(i , a , b) for(ll i = a ; i <= b ; ++i)
#define fo(i , a , b) for(ll i = a ; i >= b ; --i)
#pragma comment(linker , "/stack : 200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
inline char gchar()
{
    static char buf[1000000] , *p1 = buf , *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 1000000 , stdin) , p1 == p2) ? EOF : *p1++;
}
inline ll read()
{
    ll x = 0 , f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
	  {
        if(ch == '-')
        {
        	f = -1;
		}
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
	  {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
ll l , r;
ll f[100005] , tag;
inline ll check_l(ll L , ll R , ll x)
{
    while(L < R)
    {
        ll mid = (L + R) >> 1;
        if(f[mid] >= x)
        {
            R = mid;
        }
        else
        {
            L = mid + 1;
        }
    }
    return L;
}
inline ll check(ll L , ll R , ll x)
{
    while(L < R)
    {
        ll mid = (L + R + 1) >> 1;
        if(f[mid] <= x)
        {
            L = mid;
        }
        else
        {
            R = mid - 1;
        }
    }
    return L;
}
signed main()
{
    fr(i , 0 , 5000)
    {
        f[++tag] = f[i] * 10 + 4;
        f[++tag] = f[i] * 10 + 7;
    }
    l = read();
    ll L = check_l(0 , tag , l);
    r = read();
    ll R = check(0 , tag , r);
    if(L == R + 1)
    {
        printf("%lld" , f[L] * (r - l + 1));
        system("pause");
        return 0;
    }
    ll sum = 0 , left = (f[L] - l + 1) * f[L] , right = (r - f[R]) * f[R + 1];
    for(ll i = R - L , block = L + 1 ; i > 0 ; --i , ++block)
    {
        sum += (f[block] - f[block - 1]) * f[block];
    }
    printf("%lld", left + sum + right);
    system("pause");
    return 0;
}
/*
4 7 44 47 74 77 444 447 474 477
*/