1 条题解

  • 0
    @ 2026-11-15 17:07:43

    题目分析

    出一套 CSP-J 的题目,不仅仅只是挑出四个难度和正赛相仿的题目,更在于让刚刚涉足 OI 的同学们看到一些好的思想,好的角度。

    A 是一道找规律的题目,本身定位就是意在让选手猜出答案。实际上,在后续的 OI 各种比赛中,学会不加证明地运用某些实际正确的结论是很重要的。

    手玩几组小数据,答案明显是 n2n^2。

    实际上 f(x)f(x) 就是我们常说的 lowbit(x)\text{lowbit}(x)。

    【结论】

    $$\sum\limits_{i=k+1}^{2k}\dfrac i{\text{lowbit}(i)}=k^2$$

    【证明 1】

    令 f(x)=xlowbit(x)f(x)=\dfrac x{\text{lowbit}(x)},上面的和为 s(k)s(k)。

    • 【引理 1】 f(x)=f(2⋅x)f(x)=f(2\cdot x)
    • 【引理 2】 $\forall a\in\{x\mid x=2\cdot k+1,k\in\textbf{Z}^+\},f(a)=a$

    证明显然。

    设命题在 k=k0k=k_0 时成立,则 s(k0)=k02s(k_0)=k_0^2。

    则有

    $$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}$$

    即命题对 k=k0+1k=k_0+1 成立。

    命题对 k=1k=1 显然成立,数学归纳,得到结论成立。


    【证明 2】

    发现可以把 (k,2⋅k](k,2\cdot k] 里的所有数映射到 1∼2⋅k−11\sim 2\cdot k-1 的所有奇数,然后相加即可。需要证明如下结论:

    【结论】 (k,2⋅k](k,2\cdot k](下称 A 集)里的所有数的 ff 值恰好构成 [1,2⋅k−1][1,2\cdot k-1] 中的所有奇数(下称 B 集)。

    【证明】

    设命题对 k=k0k=k_0 成立,对于 k=k0+1k=k_0+1:

    • A 集中少了 k0+1k_0+1,多了 2⋅k0+1,2⋅k0+22\cdot k_0+1,2\cdot k_0+2。
    • B 集中多了 2⋅k0+12\cdot k_0+1。

    注意到由于引理,上述易证等价。

    即命题对 k=k0+1k=k_0+1 成立。

    命题对 k=1k=1 显然成立,数学归纳,得到结论成立。

    代码略。

    • 1

    信息

    ID
    145
    时间
    1000ms
    内存
    512MiB
    难度
    2
    标签
    递交数
    2
    已通过
    1
    上传者