/ tabris /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 7ms 512.0 KiB
#2 Accepted 6ms 508.0 KiB
#3 Accepted 3ms 472.0 KiB

代码

#include<bits/stdc++.h>

using namespace std;
const int maxn = 21;
typedef long long ll;
ll dp[maxn][maxn << 1][maxn];
int num[11] = {1,0,0,0,1,0,1,0,2,1};
int bit[maxn],n;
ll dfs(int pos,int sum,int now,int fz,int flag)
{
    if(pos <= 0) return sum;
    if(flag && dp[pos][sum][now] != -1)
        return dp[pos][sum][now];
    int up = flag ? 9 : bit[pos];
    ll ans = 0;
    for(int i = 0;i <= up;++i)
    {
        if(fz == 0)
        {
            if(i == 0)
                ans += dfs(pos-1,0,maxn-1,0,flag || i != up);
            else
                ans += dfs(pos-1,sum+num[i],i,1,flag || i != up);
        }
        else
           ans += dfs(pos-1,sum+num[i],i,fz,flag || i != up);
    }
    if(flag)
        dp[pos][sum][now] = ans;
    return ans;

}
ll solve(ll x)
{
    if(x <= 0) return 0;
    int len = 0;
    while(x)
    {
        bit[++len] = x % 10;
        x /= 10;
    }
    return dfs(len,0,maxn-1,0,0);
}
int main()
{
    ll a,b;
    int _;
    cin >> _;
    memset(dp,-1,sizeof dp);
    while(_--)
    {
        scanf("%lld %lld",&a,&b);
        printf("%lld\n",solve(b) - solve(a-1));
    }
    return 0;
}

信息

递交者
类型
递交
题目
数圈圈
语言
C++
递交时间
2017-11-22 17:19:41
评测时间
2017-11-22 17:19:41
评测机
分数
384
总耗时
17ms
峰值内存
512.0 KiB