学步园

下午满课，没推完就直接上课去了，晚上直接推敲了下，感觉确实挺简单的。  有人用数位dp做的，这种题的通解可以用数位dp的，但是这题比较特殊，可以直接推倒出结果来，考虑到每一位的时候。

solve算出的是0到a中满足条件的数的个数。

先想清楚一点： 0 ~ 99...999 如果这个都推不出来我就无语了。 例如9438298   第一位为9  则当它为8~0时，他的下面部分是完全的，所以可以9*sum[dig]，然后讨论为9的时候，继续讨论9的下一位，规律依然如此。此处需要指出的是，讨论个位的时候需要特别注意，因为他没有下一位，直接来暴力讨论，反正最大的复杂度为（10）。最后提醒一点  结果是a到b的，前闭后闭区间，所以最后是solve(b) - solve(a-1)，本人就因为这无缘无故wa了一次。

#include<cstdio>
#include<iostream>
using namespace std;
const int N = 22;
long long num[22];
int dig[N];


void ini()
{
    num[1] = 1;
    for(int i=2; i<20; ++i)
        num[i] = num[i-1]*10;
}

long long solve(long long a)
{
    long long ans = 0, sum = 0;
    int len = 0;
    while(a)
    {
        len++;
        dig[len] = a%10;
        sum += dig[len];
        a /= 10;
    }
    sum -= dig[1];
    for(int i=0; i<=dig[1]; ++i)
        if((sum+i)%10==0)
        ans++;
    for(int i=2; i<=len; ++i)
       ans += num[i-1]*dig[i];
    return ans;
}

int main(void)
{
    ini();
    int v = 0;
    int ncase;
    cin>>ncase;
    while(ncase--)
    {
    long long a,b;
    cin>>a>>b;
    long long tmp = solve(b) - solve(a-1);
    printf("Case #%d: ",++v);
    cout<<tmp<<endl;


    }
    return 0;
}