自动搬运

查看原文

来自洛谷，原作者为

	bh1234666 这蒟蒻很烂，什么都没有留下

搬运于2025-08-24 22:39:28，当前版本为作者最后更新于2022-03-25 15:47:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先考虑使两数乘积最大。

为便于描述，将两个数前均加上 $0.$ ，使其变为小数。

经过这样的变化后，有几个显然的性质：两数均在 $0.8$ 到 $1$ 之间，两数末尾的 $0$ 可以忽略，因此接下来我们可以忽略题目给出的 $0$。

设 $k=\sum c_i$，显然在变化之后的乘积是变化之前的 $10^{-k}$，与如何分配数字及如何排列无关。

假设将两数中在高位且值较大的数字跟另一数中在低位且值较小的数字交换。

设两数分别为 $a,b(0.1<a,b<1)$ 其中需要交换的两位置的值为 $x,y(0\le x < y \le 9)$,权为 $n,m(0\le n\times 10 \le m \le 0.1)$。

则交换 $x,y$ 前两数乘积为 $a\times b$。

交换 $x,y$ 后两数乘积为：

$(a-x\times n+y\times n)\times (b-y\times m+x\times m)$

$=a\times b+2\times x\times y\times n\times m-x^2\times n\times m-y^2\times n\times m+a\times m\times(x-y)-b\times n\times (x-y)$

$=a\times b - n\times m\times (x-y)^2-(x-y)\times(a\times m-b\times n)$

设 $x-y=t(-9\le t\le -1)$

则变化量（修改后减去修改前）为：

$-n\times m\times t^2-t\times(a\times m-b\times n)$

$=-t\times(n\times m\times t+a\times m-b\times n)$

其中：

$n\times m\times t+a\times m-b\times n$

$< n\times m \times (-1)+1\times m-0.1\times n$

$< m-0.1\times n$

$\le 0$

因为 $-t>0$，所以最终变化量小于。即将高位的较大的数与低位的较小的数互换结果一定更劣，所以大数必定在高位。

因此两数长度差至多为 $1$，否则违反了上述原则（存在 $0$ 所在位高于其他数）。当两数长度不等时，在短的数末尾补 $0$ 使得两数长度相同。

由于相同的权对应的能填的位置只有两个，因此我们可以确定每个数字对应的权，因此两数的和就被固定下来了。

显然，两数和一定，差越小，积越大，因此我们要分配两组数使得两数差最小。

假设两数分别为 $A$,$B$。

从高位开始分配，第一次两数分配到的数不同后，假设 $A$ 分配到了较大的数，那么由于 $A$ 高位存在大数，因此之后无论如何 $A$ 都大于 $B$，因此接下来每一组中的大的数均分配给 $B$ 。

接下来考虑如何让两数 $0 \sim 9$ 的数量不等于给定的数量。

做个卷积把两数乘起来，输出乘积和 $1$ 即可获得 70 分不会吧不会吧不会真的有人 T2 写卷积吧。

100 分:由于给定的数每个数至少有一个，因此两数必有一数以 $0$ 结尾，把它除以二另一个乘二即可。

由于两数开头一定为 $8,9$ 或 $9,9$，因此一数乘二一数除以二必定会导致一数长度加一一数长度不变，数字总数量与给定的个数不等，必定有数数量与原先不一样。

代码:

#include<stdio.h>
char s1[1000005],s2[1000005];int l1,l2;
void half(char *s,int len)
{
	int i;
	for(i=0;i<len;i++)
	{
		s[i]-='0';
		if(s[i]&1) s[i+1]+=10;
		s[i]>>=1;
		s[i]+='0';
	}
	if(s[0]=='0') puts(s+1);
	else puts(s);
}
void dble(char *s,int len)
{
	int i;_Bool fl=0;
	for(i=len-1;i>=0;i--)
	{
		s[i]-='0';
		if(s[i]>4) s[i]<<=1,s[i]-=10,s[i]+=fl,fl=1;
		else s[i]<<=1,s[i]+=fl,fl=0;
		s[i]+='0';
	}
	if(fl) putchar('1');
	puts(s);
}
int main()
{
	int i,j,a[10];_Bool flag=0;
	for(i=0;i<10;i++)
		scanf("%d",&a[i]);
	for(j=0,i=9;j<2;j++)
	{
		for(;j&&i>=0;i--)
			if(a[i])
			{
				a[i]--;
				s2[l2++]='0'+i;
				break;
			}
		for(;i>=0;i--)
		{
			while(a[i])
			{
				a[i]--;
				if(!flag) s1[l1++]='0'+i;
				else s2[l2++]='0'+i;
				flag=!flag;
			}
			if(flag&&!j) break;
		}		
	}
	if(s1[l1-1]=='0')
	{
		half(s1,l1);
		dble(s2,l2);
	}
	else
	{
		half(s2,l2);
		dble(s1,l1);
	}
	return 0;
}