NOIP2010普及组复赛 D-数字统计 处理大数据
D-数字统计_NOIP2010普及组复赛
https://ac.nowcoder.com/acm/contest/238/D
https://ac.nowcoder.com/acm/contest/238/D
https://www.nowcoder.com/study/live/249/9/2
题目如下
请统计某个给定范围[L, R]的所有整数中，数字2出现的次数。
比如给定范围[2, 22]，数字2在数2中出现了1次，在数12中出现1次，在数20中出现1次，在数21中出现1次，在数22中出现2次，所以数字2在该范围内一共出现了6次。
输入描述:
输入共1行，为两个正整数L和R，之间用一个空格隔开。
输出描述:
输出共1行，表示数字2出现的次数。
示例1
输入
2 22
输出
6
示例2
输入
2 100
输出
20
备注:
1≤L≤R≤10000。
本题数据较小，可以暴力模拟(见函数solve2(n,m))
此博客给出一个可以处理L<=R<=1e18的算法(见函数solve(n,m))，最后的注释是用于debug和检测答案正确性的
https://www.nowcoder.com/study/live/249/9/2
题目如下
请统计某个给定范围[L, R]的所有整数中，数字2出现的次数。
比如给定范围[2, 22]，数字2在数2中出现了1次，在数12中出现1次，在数20中出现1次，在数21中出现1次，在数22中出现2次，所以数字2在该范围内一共出现了6次。
输入描述:
输入共1行，为两个正整数L和R，之间用一个空格隔开。
输出描述:
输出共1行，表示数字2出现的次数。
示例1
输入
2 22
输出
6
示例2
输入
2 100
输出
20
备注:
1≤L≤R≤10000。
本题数据较小，可以暴力模拟(见函数solve2(n,m))
此博客给出一个可以处理L<=R<=1e18的算法(见函数solve(n,m))，最后的注释是用于debug和检测答案正确性的
具体思路看注释
代码格式有问题请移步https://paste.ubuntu.com/p/pPQygRbwQQ/
代码格式有问题请移步https://paste.ubuntu.com/p/pPQygRbwQQ/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long LL;
const double eps=1e-6;
LL qpow(LL x)
{ LL ans=1,base=10; while(x) { if(x&1) ans*=base; base*=base; x>>=1; } return ans;
}
LL get_len(LL x)
{ return floor(log10(x));
}
LL dfs(LL x) //0到x-1多少个2
{ // printf("x=%lld\n",x); if(x<=2) return 0; else if(x<10) return 1; else { //对于x=3256000来说 LL len=get_len(x); //6 LL t=qpow(len); //1000000 LL f=x/t; //3 LL mod=x%t; // 256000 // printf("len=%lld,t=%lld,f=%lld,mod=%lld\n",len,t,f,mod); if(mod) //此数包含不止一个非零数，如205或者3600或者200145000 return dfs(f*t)+dfs(mod)+(f==2)*mod; else if(f==1) //此数是1000..000，只包含一个1和后面的0 return dfs(x/10)*10+x/10; else //此数是200或者3000或者70000等等，只包含一个数字和后面的0 return dfs(t)*f+(f>2)*t; }
}
LL solve(LL L,LL R)
{ return dfs(R+1)-dfs(L);
}
LL solve2(LL l,LL r)
{ LL i,k,ans=0; for(i=l;i<=r;i++) for(k=i;k>0;k/=10) if(k%10==2)ans++; return ans;
}
int main()
{ LL L,R; while(cin>>L>>R) { cout<<solve(L,R)<<endl; // cout<<solve2(L,R)<<endl; } // LL x; // while(cin>>x) // printf("dfs(%lld)=%lld\n",x,dfs(x)); // while(cin>>L>>R) // for(LL i=1;i<=L;i++) // for(LL j=i;j<=R;j++) // { // if(solve(i,j)!=solve2(i,j)) // printf("ERROR:\nsolve(%lld,%lld)=%lld\nsolve2(%lld,%lld)=%lld\n\n",i,j,solve(i,j),i,j,solve2(i,j)); // else // printf("OK:L=%lld,R=%lld\n",i,j); // } return 0;
}