计数思想

这类题目是使用数组记录某些数字的出现情况，我们把它叫桶。

例如在 数字的出现次数 一题中，虽然 $n\leq 10^4$ 但是我们只需统计 $0\leq a_i\leq 9$ 这 $10$ 个数字的出现次数。因此桶的大小设定为 int a[10] 就完全够用了。

每次输入一个数字 $x$ 相当于在这个桶里写 “正”字。

for (int i = 1; i <= n; i++)
{
     cin >> x;
     a[x]++;
}

最后求每个数字的出现次数，就是输出 $0\sim 9$ 这 $10$ 个桶的大小。

for (int i = 0; i <= 9; i++)
{
     cout << a[i] << " ";
}

并且由于初始每个桶内还未记录，所以需要初始化为 $0$，因此我们将数组设置为全局变量方便初始化。

这类思想不仅仅是记录数字的出现次数，例如在 [NOIP2005 普及组] 校门外的树 中，我们使用一个大小为 $10001$ 的桶，来记录 $0\sim l$ 这些位置是否还存在树。

若第 $i$ 个位置存在数，则 $a_i=1$

否则 $a_i=0$

这都是计数思想的体现。