题面:P1179 [NOIP 2010 普及组] 数字统计 - 洛谷

---

 

一：题目解释：

        需要求一区间内数字 2 的出现次数。注意22则记为 2 次，其它没别的...

---

 

二：思路、

• 思想可以考虑动态规划
• 需要计算在每一位上数字 2 的出现次数，然后将这些次数相加
• 对于每一位，我们可以根据该位上的数字是小于、等于还是大于 2 分别来计算

---

 

三：符号定义、

 

• n:当前考虑的数字
• i:当前考虑的位(1代表个位,10代表十位,以此类推)
• div:用于获取当前位的值,例如,如果考虑十位,则div为10
• h:当前位以上的数字组成的数
• c:当前位的数字
• l:当前位以下的数字组成的数

---

 

四：公式推导、(具体公式建议自行理解)
    1.当前位数字小于2

• 如果当前位的数字小于 2 ,那么各位上不可能出现 2
• 例如,对于数字 1234,考虑百位，百位是2，但如果我们考虑十位(3)，则视为上不可能有 2
• 这种情况下,数字 2 的出现的次数为 0

    2.当前位数字等于2

• 如果当前位数字等于 2，那么数字 2 出现的次数由高位决定，低位可以是任意数字
• 例如,对于数字 1234，考虑百位，百位是 2，则 2 可以出现在 1200~1229 之间,共 30 次
• 这种情况下，数字2的出现次数为 h*div + l+1

    3.当前位数字大于2

• 如果当前位数字大于2，那么数字2可以出现在这个位上的所有可能情况
• 例如,对于数字1234,考虑千位，千位是1，运行不了(但能运行则2可以出现在2000~2999之间,共1000次)
• 这种情况下，数字2的出现次数为 (h+1)*div

---

 

五：综合公式、(c < 2 为 0)

    num = 0;
    if(c == 2)  num = h*div + l+1;
    else if(c > 2)  num = (h+1) * div;

---

 

六：示例运行、

0+135+130+124
    1   2   3   4
                (123+1)*1                                            
            (12+1)*10                                                
        1*100 + 34+1                                                   
    0
    ans = (0) + (1*100 + 34+1) + ((12+1)*10) + ((123+1)*1)
        = 0 + 135 + 130 + 124
        = 389

---

 

七：Code Ed、

//逐位计算
//时间复杂度:O(log(r))
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

inline int CD(int n, int d){
    int num = 0;
    int div = 1;
    int l,c,h = 0;
    while(n / div != 0){
        l = n - (n/div)*div;//更新低位
        c = (n/div) % 10;//当前位数字
        h = n / (div*10);//更新高位
        if(c < d){
            num += h*div;//当前位小于d,不计数
        }else if(c == d){
            num += h*div + l+1;//当前位等于d,增加 高位*div +低位+1
        }else{
            num += (h+1) * div;//当前位大于d,增加 (高位+1) * div
        }
        div *= 10;//移到下一位
    }
    return num;
}

signed main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int l,r;
    cin >> l >> r;
    int ans = CD(r, 2)-CD(l-1, 2);
    cout << ans << "\n";
    return 0;
}

已结...