同一骨架 2013 年湖北预赛 第 2 题 · P009353
按奇偶把指标减半,相当于逐位剥离零一位串;把同一位串放入另一种进制,则能描述不同幂的子集和。前者处理递推值,后者还必须证明位串次序确实对应数列次序。
前题只需沿合法正下标反复减半并累加奇数分支的贡献;后题要求第几项,不能只给编码双射,还要用最高不同位大于全部低位差来证明保序并核起始下标。
递增数列
由一些正整数构成,它们或者是 的幂,或者是若干个不同的 的幂的和,求第 项的值。
这是解答题,请在纸上写出完整过程。写完后对照解答给自己评分。
把能否选某个三的幂看成一位零一数字;排列次序与二进制整数完全对应。
先回想这道题的想法,再试试当前题。
这些数的三进制表示恰好只含数字零、一。若两个这种表示的最高不同位为第 位,该位的 大于低位差的绝对值,因此大小与对应的零一二进制数同序。序列从一开始,故第 项由 的二进制数字改按三进制读取。,所以第 项为 。
,没有最低位一。前三个指标对应 ,没有零项引起的错位。
不同幂的子集和可以用零一位串编码;先证顺序保持再换进制。
将不同幂的选择编码为零一位串,证明二进制到三进制的顺序保持,再准确换底计算大下标。
同一骨架 2013 年湖北预赛 第 2 题 · P009353
按奇偶把指标减半,相当于逐位剥离零一位串;把同一位串放入另一种进制,则能描述不同幂的子集和。前者处理递推值,后者还必须证明位串次序确实对应数列次序。
前题只需沿合法正下标反复减半并累加奇数分支的贡献;后题要求第几项,不能只给编码双射,还要用最高不同位大于全部低位差来证明保序并核起始下标。
已记下,谢谢!