[递推+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;}

版权声明：本文为博主原创文章，未经博主允许不得转载。

读书须用意，一字值千金。