/**//* 题意:问一个区间内July Number的个数,区间范围10^9 一个数,如890,不断求相邻位差,790->29->7 如果最后为7,则该数为July Number
看了watashi的,从7逆推 ,他的代码写得很好
不用存前置0的,只需存答案即可 比如7,用来生成长度为3的时候,7可看做07 只需 delta = difference/ten[n-1]; difference -= delta*ten[n-1]; 就能看做有前置0了 枚举长度 枚举第一个数字 枚举所有可以到达7的difference dfs ,每次+- difference相应位的值 */ #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<string> #include<map>
using namespace std;
int ten[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, };
vector<int> rec(1,7);// vector<int> vc;
void dfs(int n , int difference , int x , int pre) { pre = pre*10 + x; if(n==0) { vc.push_back(pre); return; } int delta = difference/ten[n-1]; difference -= delta*ten[n-1]; if(x-delta>=0)dfs(n-1,difference,x-delta,pre); if(x+delta<=9)dfs(n-1,difference,x+delta,pre); }
void init() { for(int len = 2 ; len <= 9 ; len++) { vc.clear(); for(int first = 1 ; first <= 9 ; first++) { for(vector<int>::iterator it = rec.begin() ; it != rec.end() ; it++) { dfs(len-1, *it , first , 0); } } rec.insert(rec.end() , vc.begin() , vc.end()); sort(rec.begin() , rec.end()); rec.erase(unique(rec.begin(),rec.end()) , rec.end()); } // cout<<rec.size()<<endl; }
int main() { init(); int a , b; while(cin>>a>>b) { cout<<upper_bound(rec.begin() , rec.end() , b) - lower_bound(rec.begin() , rec.end() ,a)<<endl; } return 0; }
|