1316：【例4.6】数的计数(noip2001)

### 回答1：
这道题目要求我们计算在给定的范围内，有多少个数的各个位数之和等于给定的数k。

我们可以使用循环枚举每一个数，然后计算它的各个位数之和，如果等于k，则计数器加1。

具体来说，我们可以使用两个循环，分别枚举数的十位和个位，然后计算它们的和，如果等于k，则计数器加1。

需要注意的是，当枚举十位时，如果数的个位为，则不能枚举个位，因为这样会重复计算。因此，我们需要在枚举十位时，判断个位是否为，如果是，则直接跳过个位的枚举。

最后，输出计数器的值即可。

### 回答2：
题目描述：

在一段排好序的整数序列中，统计某个整数出现的次数。

输入格式：

第1行是整数n，表示整数序列中有n个整数。第2~n+1行是整数序列中的n个整数(按升序排列)，最后一行是待查找的整数m。

输出格式：

一个整数，表示待查找的整数在序列中出现的次数。

算法思路：

由于序列已经排好序，因此可以使用二分查找的方法来查找需要统计的数。

具体方法包括以下几个步骤：

首先，在序列中使用二分查找找到第一个等于待查找数的位置，记为left；

然后，在left的左边继续使用二分查找找到第一个小于待查找数的位置，记为start；

接着，在left的右边继续使用二分查找找到第一个大于待查找数的位置，记为end；

最后，将end-start+1即为待查找数在序列中出现的次数。

需要注意的是，当左右指针相遇时，需要判断此时指针所指位置的数是否为待查找数。如果不是，则说明序列中不存在待查找数，直接返回0。

算法实现：

对于上述算法思路，可以实现如下代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int binary_search(vector<int>& nums, int target, bool flag) {
int left = 0, right = nums.size() - 1;
int idx = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
idx = mid;
if (flag) right = mid - 1;
else left = mid + 1;
}
else if (nums[mid] > target) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return idx;
}

int main() {
int n;
cin >> n;

vector<int> nums(n);
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
sort(nums.begin(), nums.end());

int target;
cin >> target;

int left = binary_search(nums, target, true);
if (left == -1) {
cout << 0 << endl;
return 0;
}
int start = binary_search(nums, target - 1, true) + 1;
int end = binary_search(nums, target + 1, false) - 1;

if (nums[left] != target) {
cout << 0 << endl;
return 0;
}

cout << end - start + 1 << endl;

return 0;
}

算法分析：

由于算法中使用到了二分查找，因此算法的时间复杂度为O(logn)；又因为算法中没有使用额外的空间，因此空间复杂度为O(1)。

从实际运行效果上来看，算法的时间复杂度是足够满足NOIP2001中数据量的要求的。

### 回答3：
题目描述：

给定正整数 n，且 n 的取值范围为 $1 \leq n \leq 10000$，请你计算从 $1\sim n$ 中所有数字中，数位含有数字 1 的数字的个数。

例如：若 n = 11，则 $1,10,11$ 均包含数字 1，所以共有 3 个数字含数字 1。

思路分析：

本题可以使用数位 DP 解决。具体来说，我们可以设 $f(i)$ 表示数字 $i$ 中数位含 1 的数字的个数。

那么对于 $\overline{a_1a_2 \cdots a_p}$（即 $i$ 只有 $p$ 位），我们可以分类讨论：当 $a_1 \neq 1$ 时，$f(i)$ 即为 $f(\overline{a_2a_3 \cdots a_p})$（即去掉最高位后的数字 $i$ 的数位含 1 的数字个数）；当 $a_1 = 1$ 时，我们可以先将最高位的 1 算上，即 $f(i) = 1 + f(\overline{a_2a_3 \cdots a_p})$。然而，还有一个问题需要解决，那就是如何统计 1~n 中数位含 1 的数字个数。这个问题可以使用类似前缀和的思路去解决：我们先计算 1~9、1~99、1~999 等各个区间中数位含 1 的数字个数，然后依次累加即可。

代码实现：