[递推+dfs]ZOJ 3436. July Number

题目大意：

将一个数字的相邻两位的差（的绝对值）组成一个新的数字。不断反复。假设最后得到7，就称这个数为July Number，比方9024 – 922 – 70 – 7。

题目要求1e9范围内给定区间[a, b]里July Number的个数。

思路：逆向递推，既然题目求能化成 7 的数的个数。那么就从 7 逆着找出去 18 。29。70，81。92等，（要注意的就是：还有从07，007.....等找出去的，每一个数同理；

代码：

/*   SKY   */

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define INF 1<<29

#define mod 1000000007

//#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int ten[] = {

	1,

	10,

	100,

	1000,

	10000,

	100000,

	1000000,

	10000000,

	100000000,

	1000000000

};

int ans[1000000],ans_;

void dfs(int cur);

void make_num(int *digit,int xx,int pre,ll nxt) //取数

{

    if(nxt>1000000000) return;

    if(xx==0){

        dfs(nxt);

        return;

    }

    xx--;

    //cout<<digit[xx]<<"-"<<pre<<endl;

    if(pre-digit[xx]>=0) make_num(digit,xx,pre-digit[xx],nxt*10+(pre-digit[xx]));

    if(pre+digit[xx]<=9&&pre-digit[xx]!=pre+digit[xx]) make_num(digit,xx,pre+digit[xx],nxt*10+(pre+digit[xx]));

}

void dfs(int cur) //逆推

{

    //cout<<cur<<"--"<<endl;

    //getchar();

    int digit[10]={0},cnt=0;

    ans[ans_++]=cur;

    while(cur){

        digit[cnt++]=cur%10;

        cur/=10;

    }

    for(int j=cnt;j<=9;j++){

        for(int i=1;i<=9;i++){

            make_num(digit,j,i,i);

        }

    }

}

int main()

{

    //freopen("mine.txt","w",stdout);

    ans_=0;

    dfs(7);

    ans[ans_++]=1000000007;

    sort(ans,ans+ans_);

//    cout<<ans_<<endl;

//    for(int i=0;i<=100;i++)

//        printf("%d\n",ans[i]);

    int l,r;

    while(cin>>l>>r){

        int R=upper_bound(ans,ans+ans_,r)-ans;

        int L=lower_bound(ans,ans+ans_,l)-ans;

        printf("%d\n",R-L);

    }

    return 0;

}