NOIP2013 TG

单项选择

13.D 分析：转换后，有效数字的位数减少了，剩下的数位会出现四舍五入的情况，那么可能增大。
15.B 分析：从$T(\frac n2)$可以得到层数最多有$\log_2^n$层，每层的计算数约等于$n$，得到时间复杂度$\mathcal{\Theta}(n\ \log n)$。

不定项选择

4.AB 分析：从定义分析：记P类问题为$p$，NP类问题为$\rm NP$，那么有$p \in \rm NP$，可知A,B两选项正确。除此之外，C选项不严谨：选项的范围对于是否在NP范围以内没有明确的表示。D选项不严谨：指数级别没有确切定义。

问题求解

2.$\frac {37}{12}$
分析：不妨用递归解决：设$f(k)$表示从第$k$个荷叶上跳到第一个荷叶上的平均步数。那么首先有：$f(1)=1$.
接着考虑递推式，可以发现：$f(k)$(以$k$为起点)到$f(i)_{1\le i\le k}$仅需一步就能跳到，所以平均应为：

$$f(k) = \frac {(\sum _{i = 1}^{n}f(i))+k}{k-1}$$

那么手动计算，即可得到答案。

阅读程序

4.7 分析：题目中给出了p个点，将其进行标记。colour函数实际上是求在规定的$(1,1)$到$(n,m)$这一矩阵中，从任意一个未被标记的一个点为起点，途中不经过任何一个已经被标记的点所能走的最长路径长度。换句话来说，给定路径集合$S = \{s_1,s_2,s_3......s_k\}$，要求$[s_i被标记] = 0(i \in [1,k]).$那么枚举即可得到结果。

完善程序

1. b[n-p+i] = a[i] 分析：此举是要将a数组的前p个元素首先挪动到b数组的后p个位置上。

6.end1 = j - 1 分析：此处讨论的情况是前i已经走到了end1但是j仍未走到end2的情况。换句话来说，讨论的是abs(end1-i) < abs(end2-j)的情况。此时，应从i开始进行下一次替换，终点为j-1。

7.count1 = j - 1 分析：此处初始化count1的值。count1是当前一个出现的数字的个数，最多应为j-1个。