数论 - 简单数位推理 --- NYIST 514

Problem's Link:http://acm.nyist.net/JudgeOnline/problem.php?pid=514


Mean:

给你一个l和r,求出在这个范围内的1的个数。

analyse:

简单的数位推理。

Time complexity:O(n) n为数字的位数

Source code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
#include<map>
#include<cstdlib>
#include<stack>
#define N 11
using namespace std;
int d[N];
int value;
void deal(int n)
{
if(n<=0) return;
int one,ten;
one=n%10;
n/=10;
ten=n;
for(int i=0;i<=one;++i)
{
d[i]+=value;
}
while(ten)
{
d[ten%10]+=(one+1)*value;
ten/=10;
}
for(int i=0;i<10;++i)
d[i]+=value*n;
d[0]-=value;
value*=10;
deal(n-1);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int s,e;
while(cin>>s>>e,s||e)
{
if(s>e)swap(s,e);
memset(d,0,sizeof d);
value=1;
deal(e);
value=-1;
deal(s-1);
cout<<d[1]<<endl;
}
return 0;
}

  

上一篇:postman本地或远程访问不了


下一篇:QT 菜单程序