1 条题解
-
0
题目分析
出一套 CSP-J 的题目,不仅仅只是挑出四个难度和正赛相仿的题目,更在于让刚刚涉足 OI 的同学们看到一些好的思想,好的角度。
A 是一道找规律的题目,本身定位就是意在让选手猜出答案。实际上,在后续的 OI 各种比赛中,学会不加证明地运用某些实际正确的结论是很重要的。
手玩几组小数据,答案明显是 。
实际上 就是我们常说的 。
【结论】
$$\sum\limits_{i=k+1}^{2k}\dfrac i{\text{lowbit}(i)}=k^2$$【证明 1】
令 ,上面的和为 。
- 【引理 1】
- 【引理 2】 $\forall a\in\{x\mid x=2\cdot k+1,k\in\textbf{Z}^+\},f(a)=a$
证明显然。
设命题在 时成立,则 。
则有
$$s(k_0+1)=s(k_0)-f(k_0+1)+f(2\cdot k_0+1)+f(2\cdot k_0+2)$$显然有 $f(k_0+1)=f(2\cdot k_0+2),f(2\cdot k_0+1)=2\cdot k_0+1$(直接运用引理得到)。
所以有
$$\begin{matrix} s(k_0+1)&=&s(k_0)+2\cdot k_0+1\\ &=&k_0^2+2\cdot k_0+1\\ &=& (k_0+1)^2 \end{matrix}$$即命题对 成立。
命题对 显然成立,数学归纳,得到结论成立。
【证明 2】
发现可以把 里的所有数映射到 的所有奇数,然后相加即可。需要证明如下结论:
【结论】 (下称 A 集)里的所有数的 值恰好构成 中的所有奇数(下称 B 集)。
【证明】
设命题对 成立,对于 :
- A 集中少了 ,多了 。
- B 集中多了 。
注意到由于引理,上述易证等价。
即命题对 成立。
命题对 显然成立,数学归纳,得到结论成立。
代码略。
- 1
信息
- ID
- 145
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 2
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者