洛谷 P1179【NOIP 2010 普及组】数字统计 —— 逐位计算

题面: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+1241   2   3   4(123+1)*1                                            (12+1)*10                                                1*100 + 34+1                                                   0ans = (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;
}

已结...