同一骨架 2025 年上海预赛 · P006370
先把对象写成不会重复的规范参数,再按控制最大值的参数分块。两题都需要同时证明块内没有重计、参数上界没有漏项,才能放心把每一块的对象数累加。
一个用增长主项给集合排序,另一个用最大项限制整数等比三元组。
将集合
中的元素从小到大排列,则第 个数为。
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
先独立尝试,再展开工具说明与想法来源。
先回想这道题的想法,再试试当前题。
二进制表示的唯一性指每个正整数只有一种由互异的二的非负整数次幂组成的和。这里指数相等会进位,须与两个非零位的情况分开。累计三角数可用 。
想法从哪来:先看哪些参数真正改变数值。正指数下零的幂已经消失,剩下两个二的幂和一个增长更快的六的幂;因此先按后者的指数分层,比直接枚举四个指数更容易排出顺序。但“集合”会去掉重复值,计数前必须证明每层的表示唯一。两个不同指数对应二进制中的两个亮位,相同指数则进位成一个亮位,这恰好给出去重理由。 接着试比较相邻两层的最大、最小值;若前层整体落在后层之前,就能先数整层,再定位层内名次。目标序号附近的累计数只差很小,最后无需把整层全部排完,只比较最小的几个幂和即可。
若直接按四元组 计数,同一个数会因 的 不同取值而被重复计算;而集合只保留互不相同的元素。因此先利用 消去不影响 数值的 ,再按最大指数 分块。块内借助二进制表示去重,块间则比较最大值与下一 块的最小值。
因为 ,所以 。又对任意满足 的 ,取 就满足 。故原集合可写成
固定 。当 时, 的二进制表示恰在第 位为 ;当 时,,其二进制表示只有一个非零位。因此不同的有序条件对 (其中 )给出不同的数。于是第 块
共有
个元素。
第 块的最大元素和第 块的最小元素分别为
对 ,有
因为 。所以第 块的所有元素都小于 第 块的所有元素,各块可以按 依次计数。
前 块的元素总数为
特别地,
因此第 个数是第 块中的第 个数。
在 时, 的最小值由 取得, 等于 ;第二小值由 取得,等于 。故所求数为
为正整数,故不存在 的歧义;取 又说明消去 后没有遗漏任何 允许的 。二进制表示保证块内没有重复,连续两块的极值比较保证块间既不交叉 也不重复。另枚举所有 的不同取值,得到前 块 恰有 个元素,第 、 个数分别为 、,与推导一致。
当题目要求排列一个由多组参数生成的集合时,首先区分“参数组数”和“不同元素个数”, 先消去不影响数值的参数并证明剩余表示是否唯一。若表达式含增长速度悬殊的主项,可按 主项指数分块,再用相邻块的极值证明块的整体顺序;最后用组合恒等式累计块大小,并在 目标所在块内作局部排序。
先消去无效参数y,再证明块内唯一和块间有序,最后由累计组合数定位第2026项,多个判断缺一不可。
同一骨架 2025 年上海预赛 · P006370
先把对象写成不会重复的规范参数,再按控制最大值的参数分块。两题都需要同时证明块内没有重计、参数上界没有漏项,才能放心把每一块的对象数累加。
一个用增长主项给集合排序,另一个用最大项限制整数等比三元组。
垫脚石(相关题 → 此题) 2025 年广西预赛 · P005913
先把有序对象切成先后不交叠的块,计算每块的对象数,再用累计块数定位目标落在哪一块。固定周期给出了最直接的练习;块大小随参数变化时,还要证明块内无重计及相邻块的整体次序。
一个按固定长度的整数周期分块,另一个按生成表达式的主参数分块;共同任务是把大下标拆成块的位置和块内的位置。
同一骨架 2026 年湖北预赛 · P006023
两题都由受限制的幂权重生成一批数,必须先区分参数组与不同结果。利用有限进位表示,或首个不同权重大于剩余可抵消权重,证明表示唯一后,才能按参数对不同结果计数或求和。
前题证明唯一性后按位置汇总总和;后题要先删去不影响结果的参数,再按主项分块排序,并检查块间的次序。
易混 2008 年河南预赛 第 9 题 · P010662
两题都借助二进制辨认不同二幂之和,但指数是否允许相等决定能否直接读取非零位。指数两两不同时可唯一恢复指数集合;允许两个指数相等时必须另查进位,并证明不同受限参数不会生成同一数。
一个将唯一表示的指数送入三角函数比较;另一个还需要分块排序和参数去重,不能把参数组数直接当不同值的个数。
同一骨架 2021 年浙江预赛 · P006926
两题都必须把“不同结果”与规范参数一一对应,才能按参数计数。合并后的单项式由指数对唯一决定;数值生成的集合则要先去冗余,并证明规范指数不会生成同一值。
变量符号的指数对自然区分单项式,而数值幂和还需唯一表示及分块极值来保证不碰撞;不能只数最初出现的参数组。
同一骨架 2025 年重庆预赛 · P006353
两题都用二进制位权证明选择与结果之间是否唯一。符号选择可先相对全正基准变成零一子集权和;两个二的幂相加时则要区分不同位与同位进位,再判断表示是否碰撞。
一个既要确定块内符号又要覆盖全部部分和,另一个还需按大主项分块并确认不同块的整体顺序,不能只数参数组。
同一骨架 2021 年上海预赛 · P007051
两题都先把对象分成有顺序的互斥块,再累计整块大小以定位目标。数位题按首次小于上界的位置分块;参数集合题则须先消去无效参数并证明表示唯一,再比较相邻块极值,确保累计的是不同元素且块间不交错。
前题的前缀自然确定整数大小,后题的主参数分块顺序需要额外证明,不能只数参数组数。
已记下,谢谢!