伤心啊,debug了一晚上,主要是是第一开始拆分数字时,没有搞对
主题思路,从最高位依次确定数字;构成模板串;
#include <cstdio> #include <set> #include <cstring> #include <cctype> #include <vector> #include <iostream> #include <algorithm> using namespace std; long long c[11]; long long d[11]; int Bit(long long x){ int cnt=0; while(x>0){ x/=10; cnt++; } return cnt; } long long solve(long long p){ if(p==1) return 1; return 9*d[p-1]+solve(p-1); } long long cal(long long n,int p,bool is_first){ if(p<=1){ return 1; } long long num = n/c[p-1]; long long res = cal(n-num*c[p-1],p-1,false); if(is_first){ res += (num-1)*(d[p-1]); res += solve(p-1); } else { res += num*d[p-1]; res += num ==0 ? (n-num*c[p-1]+1) :c[p-1]; } return res; } int main() { c[1]= 10; for(int i=2;i<=10;i++) c[i]=c[i-1]*10; d[1] = 1; for(int i=2;i<=10;i++){ d[i]=10*d[i-1]+c[i-1]; } long long n,m; while(cin>>n>>m && n>=0){ long long res1 = n==0 ? 0 : cal(n-1,Bit(n-1),true); long long res2 = cal(m,Bit(m),true); cout<<(long long)(res2 - res1)<<endl; } return 0; } void debug(){ int lim = 1091; char buf[10]; int cnt=0; for(int i=0;i<=lim;i++){ sprintf(buf,"%d",i); int len=strlen(buf); for(int j=0;j<len;j++) if(buf[j]==48) cnt++; } cout<<cal(lim,Bit(lim),true)<<endl; printf("%d\n",cnt); }