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

· · 题解

先看看题目要我们干什么。读完题后，可知题目要求给定整数 n，将 1-n 的整数排列后转换为二进制字符串拼接，输出能形成的最大二进制数对应的十进制值。

核心思路:贪心。

难点：大数处理

对于两个数 a 和 b，a 的二进制字符串 + b 的二进制字符串 > b 的二进制字符串 + a 的二进制字符串，则 a 应排在 b 前面。通过此策略排序后（好吧我不会推了），逆序拼接可得到最大二进制数。

当 n 较大时，二进制字符串可能长达数万位，无法用普通整数存储。需用字符串模拟十进制运算逐位乘 2 和加 1 实现转换。

代码实现 （呜呜呜这马蜂没救了。。。。。。）

#include<bits/stdc++.h>
using namespace std;
bool c(const string&x,const string&y){return x+y<y+x;}
string t(int n,int k){
 if(n==0)return"0";
 string a;
 while(n>0){int r=n%k;a+=r<10?r+'0':r-10+'A';n/=k;}
 reverse(a.begin(),a.end());
 return a;
}
string b2d(const string&bin){
 vector<int>d={0};
 for(char ch:bin){
  int c=0;
  for(int i=0;i<d.size();++i){int v=d[i]*2+c;d[i]=v%10;c=v/10;}
  while(c){d.push_back(c%10);c/=10;}
  if(ch=='1'){
   int ca=1;
   for(int i=0;i<d.size()&&ca;++i){int v=d[i]+ca;d[i]=v%10;ca=v/10;}
   if(ca)d.push_back(ca);
  }
 }
 string r;
 for(int i=d.size()-1;i>=0;--i)r+=d[i]+'0';
 return r;
}
int main(){
 ios_base::sync_with_stdio(false);cin.tie(0);
 int n;cin>>n;
 vector<string>s(n+1);
 for(int i=1;i<=n;++i)s[i]=t(i,2);
 sort(s.begin()+1,s.end(),c);
 string m;
 for(int i=n;i>=1;--i)m+=s[i];
 cout<<b2d(m)<<endl;
 return 0;
}

总结