[NOIP 2010 普及组] 数字统计

知识点

枚举、数位处理、计数

解题思路

遍历闭区间L到R，对每个数反复取模10获得末位；若末位为2就累加，再除以10去掉末位。各整数的贡献相加即为答案。

正确性说明

每个正整数的十进制位在不断取模与整除过程中恰好访问一次，所以该整数中的每个2都被计数一次。区间枚举不重复也不遗漏任一整数，故总和正确。

易错点

统计的是2的出现次数，不是含2的整数个数；22贡献2；区间两端都要包含；本题与统计7的教材改编题不同。

复杂度

时间O((R-L+1)log R)，额外空间O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int l,r,ans=0;cin>>l>>r;for(int x=l;x<=r;++x)for(int v=x;v;v/=10)ans+=v%10==2;cout<<ans<<'\n';}