题解：P12186 [蓝桥杯 2025 省 Python A/研究生组] 最大数字

Pufflet233 · 2025-04-16 21:48:35 · 题解

题目链接

更好的阅读体验

本题解是 Python 题解，C++ 用户可以参考本题解思路，但需自行实现高精度二进制转十进制，并且需要使用快速读入技巧。这里放出作者的 C++ 代码，不过作者码风极差，仅供参考。链接

题目简介

给一个数字 n，要求把 1, 2, 3, \cdots, n 这 n 个连续的数字转成二进制并任意排序，这些数字可以连接在一起组成一个新的二进制数字，把可以组成最大的数字用十进制输出。

解题思路

首先我们先将 1 至 n 全部数字转为二进制。

接着就是进行排序，我们这里设两个二进制字符串分别为 s_1 和 s_2。我们可以把这两个字符串拼在一起变成 s_1 + s_2 及 s_2 + s_1 进行比较，为了令到组成的数字更大，我们在两个字符串连接时肯定会选择拼成两个拼装的字符串中更大的一位，因此若 s_1 + s_2 > s_2 + s_1，我们就把 s_1 放在前面，否则把 s_1 放在后面。

例如：我现在有两个二进制字符串 10 及 11（在十进制中分别为 2 和 3），把这两个字符串连接后可以组成 1011 及 1110（在十进制分别为 11 及 14），为了组成更大的数字，我们会将 11 放在 10 前面。

代码实现

首先我们需要把 1 至 n 全部数字转成二进制，我们可以用到 bin() 函数，这个函数可以把一个整数转成二进制字符串，不过生成的字符串前面会带 0b 而我们不需要，因此我们在用这个函数的时候还需要进行切片，代码是 bin(i)[2:] 。我们只需要用循环，把每一个数转成二进制后放进一个列表即可，以下是代码。

bins=[bin(i)[2:] for i in range(1,n+1)]

然后进行排序即可，我们可以先写一个自定义比较函数。

def check(a,b):
    if a+b>b+a:
        return 0
    else:
        return 1

接着用自带的 list.sort() 函数即可，我们对一个列表可以用这个函数进行排序，默认是从小到大，如果我们需要自定义排序，需要先用 functools.cmp_to_key() 函数将比较函数转换为 key 函数，再传给 key 参数，这个函数需要导入 functools 库。下面是参考代码。

import functools #functools.cmp_to_key需要导入functools库
def check(a,b): #自定义检查函数
    if a+b>b+a:
        return -1
    else:
        return 1

bins.sort(key=functools.cmp_to_key(check)) #排序

因为组成的数字过大，因此需要修改 int 最大处理值。

import sys #导入sys库
sys.set_int_max_str_digits(0) #将Python的int最大处理值设置为无上限

下面是完整代码

import functools
import sys
sys.set_int_max_str_digits(0)
def check(a,b): #自定义检查函数
    if a+b>b+a:
        return -1
    else:
        return 1
n=int(input()) #输入
bins=[bin(i)[2:] for i in range(1,n+1)] #开一个列表，储存1到n+1全部数的二进制
bins.sort(key=functools.cmp_to_key(check)) #排序
ans=''.join(bins) #把数连接在一起
print(int(ans,2)) #输出

题解：P12186 [蓝桥杯 2025 省 Python A/研究生组] 最大数字

题目简介

解题思路

代码实现

相关题目