 /**//*
題意:問一個區(qū)間內(nèi)July Number的個數(shù),區(qū)間范圍10^9
一個數(shù),如890,不斷求相鄰位差,790->29->7
如果最后為7,則該數(shù)為July Number

看了watashi的,從7逆推 ,他的代碼寫得很好

不用存前置0的,只需存答案即可
比如7,用來生成長度為3的時候,7可看做07
只需
delta = difference/ten[n-1];
difference -= delta*ten[n-1];
就能看做有前置0了
枚舉長度
枚舉第一個數(shù)字
枚舉所有可以到達(dá)7的difference
dfs ,每次+- difference相應(yīng)位的值
*/
#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;
}


|