5 条题解

  • 3
    @ 2026-2-25 11:14:35 
    #include <bits/stdc++.h>
using namespace std;
string a,b;int a1[20],b1[20];
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>a>>b;
    for(int i=0;i<a.size();i++)a1[a[i]-48]++;
    for(int i=0;i<b.size();i++)b1[b[i]-48]++;//输入+计数 
    string x=a,y=b;int ans=0;
    for(int u=1;u<=9;u++)for(int v=1;v<=9;v++)
	{
        if(!a1[u]||!b1[v]||u+v<10)continue;//确保肯定能产生一次进位,从而达到最优 
        string A,B;
        A='0'+u;B='0'+v;//开始构造,注意转字符串时加上'0' 
        int ca[20],cb[20];
    	copy(a1,a1+10,ca);copy(b1,b1+10,cb);
        ca[u]--;cb[v]--;//把最开始配对的减去，注意以后还要构造,所以新开两数组 
        int res=1;//ans表示以前情况的最大进位数量,res表示此次进位数量 
        for(int s=9;s<=18;s++)for(int i=1;i<=9;i++)
		{
            while(1<=s-i&&s-i<=9&&ca[i]&&cb[s-i])
			{
                ca[i]--;cb[s-i]--;
                A+=i+'0';B+=s-i+'0';
                res++;
            }
        }
        /*
		这一部分枚举目标和,两个一位数的和可能范围是 2~18,但为了进位最优,必须≥10,
		但第一对数已经产生进位，所以 s可以从 9开始
		内层循环i从 1到 9找ca[i]和cb[s-i]是否都有数字,如果有就配一对,加到结果末尾。
		这一步贪心:按 s从小到大,尽可能多地配对数字,这样能最大化总对数.
		*/
        for(int i=9;i>=1;i--) 
		{
			res+=(i==9)*(ca[i]+cb[i]);
            while(ca[i]--)A+=i+'0';
            while(cb[i]--)B+=i+'0';
        }
        //剩余数字按升序追加到A和B尾,注意i=9时也算进位,因为前面的数进位加到这也会产生新的进位 
        reverse(A.begin(),A.end());
        reverse(B.begin(),B.end());//记得反过来 
        if(res>ans)
		{
            ans=res;
            x=A;y=B;
        }//比较最优 
    }
    cout<<x<<'\n'<<y;
    return 0;
}
    • 3
      @ 2026-2-25 10:17:35 
      #include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
string s;stack<int>b;
int l1,l2,a[N],sum[10];
void print()
{
    for(int i=1;i<10;i++)
        while(sum[i]>0)
        {
            printf("%d",i);
            sum[i]--;
        }
    while(b.size())
	{
	    printf("%d",b.top());
	    b.pop();
	}
    exit(0);
}
int main()
{
	getline(cin,s);l1=s.size();
	for(int i=0;i<l1;i++)a[i+1]=s[i]-'0';
	getline(cin,s);l2=s.size();
	for(int i=0;i<l2;i++)sum[s[i]-'0']++;//sum存储b中数字1至9出现的数量
	bool book=0;sort(a+1,a+l1+1);//a排序
	for(int i=1;i<=l1;i++)printf("%d",a[i]);
	puts("");//每次进位数字和会减少，因此从a的末尾开始一直凑进位
	for(int i=10-a[l1];i<10;i++)//末尾要凑10，特判
		if(sum[i]>0){b.push(i);sum[i]--;book=1;break;}
	if(!book)print();//如果不能凑出进位，随便填
	for(int i=l1-1;i>0;i--)
	{
		book=0;
		for(int j=9-a[i];j<10;j++)//末位进了位，凑9就行
			if(sum[j]>0){b.push(j);sum[j]--;book=1;break;}
		if(!book)print();//同32行 
	}
	print();return 0;
}
      • 2
        @ 2026-2-25 11:43:54
        a,b相加考虑进/不进位：a,b相加考虑进/不进位： ①不进位：S(a+b)=S(a)+S(b)①不进位：S(a+b)=S(a)+S(b) ②进位：S(a+b)=S(a)+S(b)−9②进位：S(a+b)=S(a)+S(b)-9 其中S(x)表示整数x数位和其中S(x)表示整数x数位和 所以构造的a,b应尽可能多的进位所以构造的a,b应尽可能多的进位 设a=a0+10a1+102a2+...+10nan设a=a_{0}+10a_{1}+10^{2}a_{2}+...+10^{n}a_{n} 设b=b0+10b1+102b2+...+10nbn设b=b_{0}+10b_{1}+10^{2}b_{2}+...+10^{n}b_{n} 则有a0+b0>=10，ai+bi>=9(1≤i≤n)应使得n尽可能大则有a_{0}+b_{0}>=10，a_{i}+b_{i}>=9(1≤i≤n)应使得n尽可能大 
        #include<bits/stdc++.h>
using namespace std;
#define int long long
int sum1[15],sum2[15];
string s1,s2;
struct node{
	int x,y,v;
};
vector<node>v[2];
void check(){ 
	for(int i=1;i<=9;i++)if(sum1[i]){
		for(int j=10-i;j<=9;j++){
			if(sum2[j])return;
		}
	}
	
	cout<<s1<<'\n'<<s2;//无论如何都无法进位 
	exit(0);
}
vector<int>ans1,ans2;
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>s1>>s2;
	for(int i=0;i<s1.size();i++){
		sum1[s1[i]-'0']++;
	}
	for(int i=0;i<s2.size();i++){
		sum2[s2[i]-'0']++;
	}
	check();
	for(int i=1;i<=9;i++){
		int vv=min(sum1[i],sum2[9-i]);
		v[0].push_back({i,9-i,vv});
		sum1[i]-=vv,sum2[9-i]-=vv;
	}
	for(int i=1;i<=9;i++){
		for(int j=10-i;j<=9;j++){
			int vv=min(sum1[i],sum2[j]);
			if(!vv)continue;
			v[1].push_back({i,j,vv});
			sum1[i]-=vv,sum2[j]-=vv;
		}
	}
	if(!v[1].size()){
		for(int i=0;i<v[0].size();i++){
			int x=v[0][i].x,y=v[0][i].y,vv=v[0][i].v;
			if(!vv)continue;
			bool bk=0;
			for(int j=1;x+j<=9;j++)if(x+y+j>=10&&sum1[x+j]){
				v[0][i]={x,y,vv-1};
				v[1].push_back({x+j,y,1});
				sum1[x]++;
				sum1[x+j]--;
				bk=1;
				break;
			}
			if(bk)break;
			for(int j=1;y+j<=9;j++)if(x+y+j>=10&&sum2[y+j]){
				v[0][i]={x,y,vv-1};
				v[1].push_back({x,y+j,1});
				sum2[y]++;
				sum2[y+j]--;
				bk=1;
				break;
			}
			if(bk)break;
		}
	}
	
	for(int i=1;i<=9;i++){
		for(int j=1;j<=sum1[i];j++)cout<<i;
	}
	for(node i:v[0]){
		for(int j=1;j<=i.v;j++)cout<<i.x;	
	}
	for(node i:v[1]){
		for(int j=1;j<=i.v;j++)cout<<i.x;
	}
	cout<<'\n';
	for(int i=1;i<=9;i++){
		for(int j=1;j<=sum2[i];j++)cout<<i;
	}
	for(node i:v[0]){
		for(int j=1;j<=i.v;j++)cout<<i.y;
	}
	for(node i:v[1]){
		for(int j=1;j<=i.v;j++)cout<<i.y;
	}
	
	return 0;
}
        • 2
          @ 2026-2-25 11:43:51 
          首先本题要求两数相加后所得的数各位数字之和最小
怎么样才能做到最小呢？
不妨设sum为原本两数各位数字之和的和,ans为最终答案,x为两数相加之和 
为什么ans会比sum小呢?
因为相加时会有进位
每次进位都会使ans减9
所以核心思路为尽量进位
在两数相加的结果中，9为比较特殊的存在
因为如果后面能往前进1的话，9也能接着往前进位
所以我们不妨把所有x中的9放在一起，然后吧10以上的数放在9的后面(其它数随便放)
9的优先级最先
 
但还有一种特殊情况 
万一把9弄完后没有其他数来进位了呢？
所以我们需要特判 
*/ 
#include<bits/stdc++.h>
using namespace std;
int ac[10],bc[10];//ac[i]代表a字符串中"a"的个数，bc同理 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string a,b;
	cin>>a>>b;//输入 
	int n=a.size(),m=b.size();
	for(int i=1;i<=9;i++)
	{
		ac[i]=bc[i]=0;
	}
	for(int i=0;i<n;i++)
	{
		ac[a[i]-'0']++;
	}
	for(int i=0;i<m;i++)
	{
		bc[b[i]-'0']++;
	}
	string a1,b1;
	a1=b1="";
	bool f=0;
	for(int k=9;k<=18;k++)
	{
		for(int i=max(k-9,1);i<=9;i++)
		{
			int j=k-i;
			int x=min(ac[i],bc[j]);//只能贡献较小的数量 
			if(x)
			{
				f|=(k>9);//这里记录一下是否都是9 
				a1+=string(x,i+'0');//这句话是指在a1后面加入x个"i"; 
				b1+=string(x,j+'0');//同上 
				ac[i]-=x,bc[j]-=x;//最终减去做贡献的位 
			}
		}
	}
	if(!f&&a1!=""&&b1!="")//注意这里需要特判a1与b1不为空,可能相加结果既没9也没10以上 
	{
		a1=b1="";//初始化 
		for(int i=1;i<=9;i++)
		{
			ac[i]=bc[i]=0;
		}
		for(int i=0;i<n;i++)
		{
			ac[a[i]-'0']++;
		}
		for(int i=0;i<m;i++)
		{
			bc[b[i]-'0']++;
		}//重新计算 
		int p,t;
		for(int k=10;k<=18;k++)//从10开始 
		{
			if(f)
			{
				break;
			}
			for(int i=k-9;i<=9;i++)
			{
				if(f)
				{
					break;
				}
				int j=k-i;
				int x=min(ac[i],bc[j]);
				if(x)
				{
					f=1;
					p=i;
					t=j;
					ac[i]--;
					bc[j]--;
				}//只需一个10以上做贡献即可 
			}
		}
		int k=9;
		for(int i=1;i<=9;i++)
		{
			int j=k-i;
			int x=min(ac[i],bc[j]);
			if(x)
			{
				a1+=string(x,i+'0');
				b1+=string(x,j+'0');
				ac[i]-=x,bc[j]-=x;
			}
		}//把所有的9再次添入a1与b1中 
		if(p&&t)
		{
			a1+=string(1,p+'0');
			b1+=string(1,t+'0');//加上做最终进位贡献的数 
		}
	}
	string c,d;
	for(int i=1;i<=9;i++)
	{
		if(ac[i])
		{
			c+=string(ac[i],i+'0');//统计剩余的位 
		}
	}
	for(int i=1;i<=9;i++)
	{
		if(bc[i])
		{
			d+=string(bc[i],i+'0');//同上 
		}
	}
	cout<<c<<a1<<endl<<d<<b1;//最终输出 
	return 0;
}
          • 0
            @ 2026-2-25 8:53:00 
            #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int c1[15],c2[15];
struct N{
	int x,y,v;
};
vector<N> v[15];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s1,s2;
	cin>>s1>>s2;
	for(char i:s1){
		c1[i-'0']++;
	}
	for(char i:s2){
		c2[i-'0']++;
	}
	string a1="",a2="";
	for(int k=10;k>=2;k--){
		for(int i=0;i<=9;i++){
			int vv=min(c1[i],c2[k-i]);
			v[k].push_back({i,k-i,min(c1[i],c2[k-i])});
			c1[i]-=vv;c2[k-i]-=vv;
		}
	}
	for(int i=0;i<=9;i++){
		for(int j=0;j<c1[i];j++)cout<<i;
	}
	for(int k=2;k<=10;k++){
		for(N i:v[k]){
			for(int j=0;j<i.v;j++)cout<<i.x; 
		}
	}
	cout<<'\n';
	for(int i=0;i<=9;i++){
		for(int j=0;j<c2[i];j++)cout<<i;
	}
	for(int k=2;k<=10;k++){
		for(N i:v[k]){
			for(int j=0;j<i.v;j++)cout<<i.y; 
		}
	}
	return 0;
}
            • 1

            [ARC130C] Digit Sum Minimization

            信息

            ID
            2517
            时间
            2000ms
            内存
            1024MiB
            难度
            8
            标签
            递交数
            53
            已通过
            9
            上传者
            1. Language
            2. 兼容模式
            3. 主题
            3. Worker 0, 13ms
            4. Powered by Hydro v5.0.1 Community