题目传送门
思路提供
首先我们可以从题目给出的部分分入手,先拿到 $50$ 分,这个我们可以通过贪心的手段保证两个数字的总和相同(因为只要保持相同就可以使得两个数的乘积最大),所以每次将数字加在总分较少的字符串上就可以保证两个字符串表示的数字的乘积最大,如果出现两个两个字符串内所有数字的总和相同的情况,就默认加在第一个的字符串里,这样就可以列举出两个保证最大乘积的字符串,而我们看到题目中保证会有一个 $0$ 的出现,而我们要使乘积不变,而改变两个数,所以我们考虑一个 $0$(可以拆成一个 $2$ 和一个 $5$ 的乘积)这样的话,我们只要去掉一个末尾的 $0$(即除去一个 $10$),再将剩下的数一个乘上 $2$,一个乘上 $5$ 就能保证总乘积不变,而考虑本题的数据范围过大,所以我们需要加上一个高精乘低精的高精度运算即可(可借鉴模板题)。
AC code
#include<bits/stdc++.h>
using namespace std;
string ans1,ans2;//分别记录答案,string十分方便
int num[15];
int tot,a[100000005];
int al[10000005],b[10000005],c[10000005];//数组要开大一些
void sh(string x,int y){//高精乘低精的模板
memset(a,0,sizeof(al));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
int s11=x.length();
for(int i=0;i<s11;i++)
al[i]=x[s11-i-1]-'0';
for(int i=0;i<s11;i++){
c[i]=al[i]*y;
}
int s3=s11+1;
for(int i=0;i<s3;i++){
c[i+1]+=c[i]/10;
c[i]%=10;
}
for(;!c[s3]&&s3>0;){
s3--;
}
while(c[s3]==0&&s3>=1) s3--;//去除前导零
for(int j=s3;j>=0;j--){
cout<<c[j];
}
cout<<endl;
}
signed main(){
for(int i=0;i<=9;i++){
cin>>num[i];
for(int j=1;j<=num[i];j++){
tot++;
a[tot]=i;
}
}
ans1+=a[tot]+'0';
ans2+=a[tot-1]+'0';//各自先加上一个数
int tot1=a[tot],tot2=a[tot-1],flag=1;
if(tot1==tot2) flag=0;
for(int i=tot-2;i>1;i--){
if(i-1>1){
if(tot1<tot2){
ans1+=a[i]+'0';
ans2+=a[i-1]+'0';
}
else if(tot1>tot2){
ans1+=a[i-1]+'0';
ans2+=a[i]+'0';
}//考虑总分不同
else{
if(flag==0 && a[i]!=a[i-1]){
tot1=a[i];
tot2=a[i-1];
flag=1;
}//相同的情况进行考虑
ans1+=a[i]+'0';
ans2+=a[i-1]+'0';
}
i--;
}
else{
if(tot1<=tot2){
ans1+=a[i]+'0';
tot1+=a[i];
}
else{
ans2+=a[i]+'0';
tot2+=a[i];
}
}
}
sh(ans1,2);
sh(ans2,5);//最后的输出
return 0;
}
标签:s3,乘积,int,Number,--,P8482,字符串,string
From: https://www.cnblogs.com/is-02/p/17686684.html