/ tabris /

记录详情

Accepted

/in/foo.cc:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:102400000000,102400000000")
 
# 状态 耗时 内存占用
#1 Accepted 7ms 472.0 KiB
#2 Accepted 7ms 504.0 KiB
#3 Accepted 3ms 504.0 KiB

代码

#pragma comment(linker, "/STACK:102400000000,102400000000")
#include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N = 1e5+8;
/****************************************************/

LL a,b;
    //   0 1 2 3 4 5 6 7 8 9
int h[]={1,0,0,0,1,0,1,0,2,1};
void bruteforce(){
    LL sum = 0;
    for(LL i = a;i<=b;i++){
        LL tem = i;
        while(tem) sum+=h[tem%10],tem/=10;
    }
    printf("%lld\n",sum);
}

int len ,num[20];
LL dp[20][12][40];

LL dfs(int pos,int fir,bool limit,bool zero,int sum){
    if(pos<0) return sum;

    LL &d = dp[pos][fir][sum];
    if(!limit && d!=-1) return d;
    int endi = 9;if(limit) endi = num[pos];
    LL res = 0;
    for(int i=0;i<=endi;i++){
        if(zero){
            if(i == 0)
                res += dfs(pos-1,10,limit&&i==endi,1,0);
            else
                res += dfs(pos-1, i,limit&&i==endi,0,h[i]);
        }
        else {
            res += dfs(pos-1,fir,limit&&i==endi,0,sum+h[i]);
        }
    }

    if(!limit) d = res;
    return res;
}

LL solve(LL n){
    len = 0;
    while(n){
        num[len++]=n%10;
        n/=10;
    }
    return dfs(len-1,10,1,1,0);
}

int main(){
//    freopen("sqq3.in","r",stdin);
//    freopen("sqq3.out","w",stdout);

    memset(dp,-1,sizeof(dp));
    int _ = 1;
    for(scanf("%d",&_);_--;){
        scanf("%lld%lld",&a,&b);

//        bruteforce();
        printf("%lld\n",solve(b)-solve(a-1));
    }
    return 0;
}

信息

递交者
类型
递交
题目
数圈圈
语言
C++
递交时间
2017-11-21 13:04:38
评测时间
2017-11-21 13:07:58
评测机
分数
384
总耗时
18ms
峰值内存
504.0 KiB