2022-08-26 13:02:02
如何求最大乘积
我们令 \(num1\) 为前几位较大的数， \(num2\) 为前几位相对较小的数。
浅浅地证明
首先我们肯定得使高位尽可能大，那么在高位都尽可能大的情况下，两个数的和基本相同的，我们用小学求周长相同，求最大矩形面积的方法，可以知道，当两数差最小时，乘积最大。
构造方法
根据上述原则，我们可以开始构造了。
当两数数位相同且前几位相同时，为了保证 \(num1\) 前几位尽可能大，我们就将最大位给 \(num1\) 即可。数位不一样，那就哪个少给哪个。当两数数位相同但数不相同时，此时 \(num1\) 的前几位已经比 \(num2\) 大了，故将大的给 \(num2\) 以保证两数差距最小。
结合代码理解一下
Code 1
tot1=tot/2; //num1的数位
tot2=tot/2+(tot&1);//num2的数位，若是奇数则将多余的给num2
int k1=0,k2=0,la1=0,la2=0;//k是已分配的位数，la是前几位相同的最后一位或者第一个不相同的那位的值
for(re int i=9;i>=0;--i){
for(;a[i];){ //num1,num2都是用队列存的
if(k1==tot1)num2.push(i),a[i]--,k2++; //若已经达到了位数就不加了
else if(k2==tot2)num1.push(i),a[i]--,k1++;
else if(k1==k2){//如果数位相同，那就看前几位相同不相同
if(la1==la2){
num1.push(i),a[i]--,k1++,la1=i;
if(a[i])num2.push(i),a[i]--,k2++,la2=i;//相同就给1
else{
for(;!a[i]&&i>=0;)--i;
if(i>=0)num2.push(i),a[i]--,k2++,la2=i;//给2
}
}
else num2.push(i),a[i]--,k2++;
}else if(k1>k2)num2.push(i),a[i]--,k2++;//谁少了给谁
else if(k1<k2)num1.push(i),a[i]--,k1++;
}
}
恭喜你，拿到了 \(50\) 分！
如何构造
在我打算放弃之际，我看见了题面中我的救星。
\(1\le c_i\)
这意味着什么？意味着一定有 \(0\) 存在，也就是其中一个数一定可以被10整除。
根据我们上面的贪心策略， \(0\) 一定被放在了末位，那么我们只需要将有 \(0\) 的那个数去掉末尾的 \(0\) ，然后再给任意一个数乘 \(5\)，另外一个数乘 \(2\)即可。
注意数据很大，得用高精。
其实乘 \(2\) 除 \(2\)，乘 \(5\) 除 \(5\) 等方法都能合理构造，只不过作者太懒不想多写一个高精除。
Code
#include<bits/stdc++.h>
using namespace std;
#define re register
inline int read(){
int x=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
return x;
}
int a[10],tot;
queue<int>num1,num2;
int tot1,tot2;
int x[10000005],y[10000005];
inline void chen(int b[],int &g,int v,int k){
for(re int i=k;i<=g;++i){
b[i]*=v;
}
for(re int i=k;i<=g;++i){
b[i+1]+=b[i]/10;
b[i]%=10;
}
for(;b[g+1]||b[g+2];)g++;
return;
}
int main(){
for(re int i=0;i<=9;++i){
a[i]=read();
tot+=a[i];
}
tot1=tot/2; //num1的数位
tot2=tot/2+(tot&1);//num2的数位，若是奇数则将多余的给num2
int k1=0,k2=0,la1=0,la2=0;//k是已分配的位数，la是前几位相同的最后一位或者第一个不相同的那位的值
for(re int i=9;i>=0;--i){
for(;a[i];){ //num1,num2都是用队列存的
if(k1==tot1)num2.push(i),a[i]--,k2++; //若已经达到了位数就不加了
else if(k2==tot2)num1.push(i),a[i]--,k1++;
else if(k1==k2){//如果数位相同，那就看前几位相同不相同
if(la1==la2){
num1.push(i),a[i]--,k1++,la1=i;
if(a[i])num2.push(i),a[i]--,k2++,la2=i;//相同就给1
else{
for(;!a[i]&&i>=0;)--i;
if(i>=0)num2.push(i),a[i]--,k2++,la2=i;//给2
}
}
else num2.push(i),a[i]--,k2++;
}else if(k1>k2)num2.push(i),a[i]--,k2++;//谁少了给谁
else if(k1<k2)num1.push(i),a[i]--,k1++;
}
}
for(re int i=1;i<=tot1;++i){
x[tot1-i+1]=num1.front();
num1.pop();
}
for(re int i=1;i<=tot2;++i){
y[tot2-i+1]=num2.front();
num2.pop();
}
k1=1,k2=1;//起始位置
if(x[1]==0)k1++;//只需去掉一个0,也就是将起始位置加一
else if(y[1]==0)k2++;
chen(x,tot1,2,k1);//高精不多说了
chen(y,tot2,5,k2);
for(re int i=tot1;i>=k1;--i){
printf("%d",x[i]);
}
puts("");
for(re int i=tot2;i>=k2;--i){
printf("%d",y[i]);
}
return 0;
}
恭喜你，满分了！