自动搬运

查看原文

来自洛谷，原作者为

	shenliyan with Accepted_cyx||花开花落，潮起潮落，日升日落......一切都是那么美好呀~||ISFJ人格||宣团（https://www.luogu.com.cn/team/101967）

搬运于2025-08-24 23:13:31，当前版本为作者最后更新于2025-06-05 22:12:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先看看题目要我们干什么。读完题后，可知题目要求给定整数 $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;
}

总结

• 贪心策略是排序的核心，通过比较拼接结果确定顺序。
• 大数处理是关键，避免直接使用整数导致溢出，需用字符串模拟运算。
• 逆序拼接是排序后得到最大结果的必要步骤。