不忘初心
时刻前行

我不可能初赛退役 (flag

NOIP 2018 提高组初赛

选择题

7 题

在一条长度为 1 的线段上随机取两个点,则以这两个点为端点的线段的期望长度是( )。


8 题

关于 Catalan 数 C_n = \frac{(2n)!}{(n + 1)!n!},下列说法中错误的是( )。

A. C_n 表示有 n + 1 个结点的不同形态的二叉树的个数。

B. C_n 表示含 n 对括号的合法括号序列的个数。

C. C_n 表示长度为 n 的入栈序列对应的合法出栈序列个数。

D. C_n 表示通过连接顶点而将 n + 2 边的凸多边形分成三角形的方法个数。


卡特兰数是一种经常出现的组合数,其通项公式为

C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}

其递推公式为

C_{n + 1} = \frac{4n+2}{n+2}C_n

Catalan 数应用很广,以下有几个经典的例子

  • 表示有多少种长度为 2n,且仅由 n 个 X, n 个 Y 组成的字符串,满足所有前缀 X 的数量大于 Y
  • 即也是 n 组括号合法的括号序列的个数(这是最重要的)
  • n 个节点的不同构二叉树个数
  • 2n+1 个节点的不同构满二叉树个数
  • n*n 个格点中,不越过对角线,只能向右或向上走的路径条数
  • n+2 边形通过连接对角线分成 n 个三角形的方案数
  • 用个长方形填充一个高度为n的阶梯状图形的方法个数
  • 在栈中将长度为 n 的序列插入与弹出的不同方案个数

不定向

11 题

NOIP CSP 初赛中,选手可以带入考场的有


认证者进入考场时,监考员检查认证者携带物品

认证者只许携带笔、橡皮等非电子文具以及饮用水和食品入场

禁止携带任何电子产品或机器设备入场,无存储功能的手表除外;

手机(关机)、U盘或移动硬盘、键盘、鼠标、闹钟、计算器、书籍、草稿纸及背包等物品必须存放在考场外

如有违规带入的,一经发现,CSP-JS认证总负责人可直接取消违规认证者的参加资格

15 题

下列关于图灵奖的说法中,正确的有()。

  1. 图灵奖是由电气和电子工程师协会(IEEE)设立的。

  2. 目前获得该奖项的华人学者只有姚期智教授一人。

  3. 其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。

  4. 它是计算机界最负盛名、最崇高的一个奖项,有“计算机界的诺贝尔奖”之称。

关于图灵奖

  • 其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵(Alan M. Turing)然而我看得所有翻译都是阿兰-图灵
  • 因此它是计算机界最负盛名、最崇高的一个奖项,有“计算机界的诺贝尔奖”之称
  • 从1966年至2019年共73名获奖者
  • 图灵奖是美国计算机协会于1966年设立的

问题求解

17 题

方程 b = (a \text{ or } b) * (a \text{ and } b),在 a, b 都取 [0, 31] 中的整数时,共有_____组解


对于任意非负整数 a_i,都有:

\min(a, b) \leq a \text{ or } b \leq \max(a, b) \leq a \text{ and } b < 2 * \max(a, b)

对于上述等式,当且仅当 a \text{ or } b = \min(a, b), a \text{ and } b = \max(a, b) 时成立

接下来我们按位考虑

不妨令 a \geq b

那么有 b 二进制下所有为 1 的位数,在 a 中都为 1

类似 ba 的子集

[0, 31] 恰意味最多二进制下有 5 位,那么我们枚举 a 有多少位为 1

具体来说,当 ak 位为 1 时,b2^k

当然,交换 a, b 之后也能得到一组新解

所以答案为

2 * \sum_{i = 0}^5 \Big(\binom{5}{i} * 2^i\Big) - 32

减去 32 意为要再减去所有 a = b 的解,因为这种情况被我们算了两遍

故答案为 454

NOIP2017 提高组初赛

选择

第 2 题

在 8 位二进制补码中,10101011 表示的数是十进制下的( )。


关于源码,反码,补码:

计算机在储存数是,第一位(最左边)用于存储符号,1 表示负,0 表示正,那么这符号位与其真值组成的二进制数即为其源码

举例:

8 位下,23 的源码为 00010111-23 的源码码为 10010111

任何正数的反码,补码都是其本身

负数的反码就是对于除符号位以外的每一位都取反

-23 的反码:11101000

负数的补码就是反码 +1

第 3 题

分辨率为 1600x900、16 位色的位图,存储图像信息所需的空间为( )。


1 B = 8 bit(位), 1 KB = 1024 B,剩下的的都是以 1024 为进率

那么 16 位色代表每一个像素都要 16 位,则其需要 1600 * 900 * 16 bit,等于 1600 * 900 * 16 / 8 /1024 = 2812.5 KB

第 6 题

若某算法的计算时间表示为递推关系式: T(N) = 2T(N / 2) + N \log N, T(1) = 1 则该算法的时间复杂度为( )。


对于此类递推问题,可以画图理解

N 往下画,共有 \log N 层,最低下为 1,每层增加 N * 2^{-k} \log N*2^{-k},其中 k 表示该层为从 N 向下数的第 k

那么和为

\sum_{k = 1}^{\log N} 2^{-k}N \log 2^{-k}N

故应该为 N \log^2N

第 10 题

f(0) = 0, f(1) = 1, f(n + 1) = \frac{f(n - 1) + f(n)}{2},则随着 i 的增大,f(i) 将接近于( )。


其特征方程为 x^2 = \frac{x + 1}{2},解得 x_1 = 1, x_2 = - \frac{1}{2}

\begin{cases} \alpha - \frac{\beta}{2} = 0 \\ \alpha + \frac{\beta}{4} = 1 \end{cases}

解得

\begin{cases} \alpha = \frac{2}{3} \\ \beta = \frac{4}{3} \end{cases}

\therefore

f(n) = \frac{2}{3} + \frac{4}{3} * (-\frac{1}{2})^n

\therefore

\lim_{n \rightarrow \infty} f(n) = \frac{2}{3}

OI-数学-组合计数

JX 11-5 校内模拟赛赛后题解与总结
上一篇 «
10.8 嘉祥校内模拟赛赛后题解与总结
» 下一篇
© 2019 - 2019 bwt's blog.
...... visits · ...... visitors