M_sea

CF1036C Classy Numbers
CodeForcesLuogu分析震惊!Edu场C题竟被评成紫题!其实就是个数位DP。设$f[i][j]$表示前i...
扫描右侧二维码阅读全文
24
2018/10

CF1036C Classy Numbers

CodeForces

Luogu

分析

震惊!Edu场C题竟被评成紫题!

其实就是个数位DP。

设$f[i][j]$表示前i位有j个非0数的数的个数。

然后按套路搞就好了。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int a[30];
int f[20][30]; //f[i][j]表示前i位有j个非0数的数的个数

inline int Dfs(int pos,int cnt,int limit) {
    if (cnt>3) return 0;
    if (!pos) return 1;
    if (!limit&&f[pos][cnt]!=-1) return f[pos][cnt];
    int tmp=0,up=limit?a[pos]:9;
    for (re int i=0;i<=up;i++) tmp+=Dfs(pos-1,cnt+(i>0),limit&&(i==up));
    return f[pos][cnt]=tmp;
}

inline int solve(int x) {
    memset(f,-1,sizeof(f));
    int l=0;
    while (x) a[++l]=x%10,x/=10;
    return Dfs(l,0,1);
}

mainint main() {
    int T=read();
    while (T--) {
        int a=read(),b=read();
        printf("%I64d\n",solve(b)-solve(a-1)); //cf要用I64 qwq
    }
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 54 PM

发表评论