NOIP 2007 普及组 小记¶
约 677 个字 预计阅读时间 2 分钟
第 14 题¶
要计算 23|2^5，由于 ^ 运算符优先级高于 |，故先将 2 与 5 转换为二进制，并进行按异或运算：
同理，对 23 与 7 进行按位或运算：
因此，值为 23。
第 15 题¶
对于 !((a!=0)&&(b!=0)&&(c!=0)) 表达式，去除最外层括号并对内取非，得 (a == 0)||(b == 0)||(c == 0)。
第 21 题¶
题目：将 \(n\) 个数 \((1, 2, \ldots, n)\) 划分成 \(r\) 个子集。每个数都恰好属于一个子集，任何两个不同的子集没有共同的数，也没有空集。将不同划分方法的总数记为 \(S(n, r)\)。例如，\(S(4, 2) = 7\)，这 \(7\) 种不同的划分方法依次为 \(\{(1), (234)\},\{(2), (134)\},\{(3), (124)\},\{(4), (123)\}，\{(12), (34)\}, \{(13), (24)\}, \{(14), (23)\}\)。 当 \(n = 6, r = 3\) 时，\(S(6, 3) = ?\) （提示：先固定一个数，对于其余的 \(5\) 个数考虑 \(S(5, 3)\) 与 \(S(5, 2)\)，再分这两种情况对原固定的数进行分析。）
我们先假设已知 \(n - 1\) 个球放置的情况数（\(S(n - 1, i)\)），如果如今要多加入一颗球，那么有两种情况：
-
将新加入的一颗球放入原来已有的“箱子”（即划分的一个数堆）中， 这种情境下情况数为 \(S(n - 1, r)*r\)。
-
让新加入的球单独占一个“箱子”，余下 \(r - 1\) 个“箱子”来放其余的球，则情况数为 \(S(n - 1, r - 1)\)。
由上可推出：
接下来，根据以上信息，要求得 \(S(6, 3)\)，我们需要得知 \(S(5, 3)\) 及 \(S(5, 2)\) 的值，而不难发现，\(S(n, 1) = 1, S(n, n) = 1\)，因此：
又由于题目给出了 \(S(4, 2) = 7\)，于是：
最后，\(S(6, 3) = S(5, 3)*3 + S(5, 2) = 25*3 + 15 = 90\)。
第 22 题¶
题目：某城市的街道是一个很规整的矩形网络（见下图），有 \(7\) 条南北向的纵街，\(5\) 条东西向的横街。现要从西南角的 \(A\) 走到东北角的 \(B\) ，最短的走法共有多少种？
首先，不难发现，无论如何走，最短的路径总是包含 \(6\) 条横街和 \(4\) 条纵街。也就是说，接下来，我们只需要考虑横纵街的不同互相搭配方式即可。
那么，答案则为 \(C\binom{4}{10} = 210\)（从十条街道中选出四条纵街）。