 /**//*
题意:问一个区间内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;
}


|