专栏文章

P13707 Higher Arithmetic 题解

AARIS0_0
P13707题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@min1tz0p
此快照首次捕获于
2025/12/01 19:11
3 个月前
此快照最后确认于
2025/12/01 19:11
3 个月前
查看原文

1. 题意解释

给出 nn 个数，使用加号乘号括号组成一个合法表达式，使得表达式的值最大，你只需要输出这个表达式。

2. 思路

假如没有 11 时，我们容易知道将所有数相乘显然是更优的。
假如有 11 时，我们还需要考虑 22 的情况。
如果 11 的个数小于等于 22 的个数，我们把 11 和 22 两两相加，剩余全部相乘。
如果 11 的个数大于 22 的个数，依然是先把 11 和 22 两两配对，对剩余的 11 作讨论。
记 11 的个数为 cntcnt。
若 cnt=1cnt=1，则将 11 与剩余数中的最小值相加。
若 cnt≡1(mod3)cnt\equiv1\pmod 3 且 cnt≠1cnt\ne1，则我们拆成 cnt−43\dfrac{cnt-4}{3} 个 33 和 22 个 22。
若 cnt≡2(mod3)cnt\equiv2\pmod 3，则我们拆成 cnt−23\dfrac{cnt-2}{3} 个 33 和 11 个 22。
若 cnt≡0(mod3)cnt\equiv0\pmod 3，则我们拆成 cnt3\dfrac{cnt}{3} 个 33。
然后将所有的这些数两两相乘即可。
最后步骤就是极其麻烦的表达式输出……
Hack 数据很多，造几个 11 和 22 可以帮你查出大部分错误。

3. 代码实现

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[100100],cnt1,cnt2;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		if(a[i]==1){
			cnt1++;
		}
		if(a[i]==2){
			cnt2++;
		}
	}
	if(n==1){
		cout<<a[1];
	}
	else{
		if(cnt1<=cnt2){
			if(cnt1>0){
				if(cnt2>0){
					cout<<"(1+2)";
					for(int i=1;i<=cnt1-1;i++){
						cout<<"*(1+2)";
					}
					for(int i=cnt1*2+1;i<=n;i++){
						cout<<"*"<<a[i];
					}
				}
				else{
					cout<<a[1];
					for(int i=2;i<=n;i++){
						cout<<"*"<<a[i];
					}
				}
			}
			else{
				for(int i=1;i<n;i++){
					cout<<a[i]<<"*";
				}
				cout<<a[n];
			}
		}
		else{
			int cnt=cnt1-cnt2;
			if(cnt%3==1){
				if(cnt==1){
					if(cnt2>0){
						cout<<"(1+1+2)";
						for(int i=1;i<=cnt2-1;i++){
							cout<<"*(1+2)";
						}
						for(int i=1;i<=cnt/3-1;i++){
							cout<<"*(1+1+1)";
						}
						for(int i=cnt1+cnt2+1;i<=n;i++){
							cout<<"*"<<a[i];
						}
					}
					else{
						cout<<"(1+"<<a[2]<<")";
						for(int i=3;i<=n;i++){
							cout<<"*"<<a[i];
						}
					}
				}
				else{
					if(cnt2>0){
						cout<<"(1+2)";
						for(int i=1;i<=cnt2-1;i++){
							cout<<"*(1+2)";
						}
						for(int i=1;i<=cnt/3-1;i++){
							cout<<"*(1+1+1)";
						}
						cout<<"*(1+1)*(1+1)";
						for(int i=cnt1+cnt2+1;i<=n;i++){
							cout<<"*"<<a[i];
						}
					}
					else{
						if(cnt/3>1){
							cout<<"(1+1+1)";
							for(int i=1;i<=cnt/3-2;i++){
								cout<<"*(1+1+1)";
							}
							cout<<"*(1+1)*(1+1)";
							for(int i=cnt1+cnt2+1;i<=n;i++){
								cout<<"*"<<a[i];
							}
						}
						else{
							cout<<"(1+1)*(1+1)";
							for(int i=cnt1+cnt2+1;i<=n;i++){
								cout<<"*"<<a[i];
							}
						}
					}
				}
			}
			if(cnt%3==2){
				if(cnt2>0){
					cout<<"(1+2)";
					for(int i=1;i<=cnt2-1;i++){
						cout<<"*(1+2)";
					}
					if(cnt/3>0){
						cout<<"*";
						for(int i=1;i<=cnt/3;i++){
							cout<<"(1+1+1)*";
						}
						cout<<"(1+1)";
					}
					else{
						cout<<"*(1+1)";
					}
					for(int i=cnt1+cnt2+1;i<=n;i++){
						cout<<"*"<<a[i];
					}
				}
				else{
					for(int i=1;i<=cnt/3;i++){
						cout<<"(1+1+1)*";
					}
					cout<<"(1+1)";
					for(int i=cnt1+cnt2+1;i<=n;i++){
						cout<<"*"<<a[i];
					}
				}
			}
			if(cnt%3==0){
				if(cnt2>0){
					cout<<"(1+2)";
					for(int i=1;i<=cnt2-1;i++){
						cout<<"*(1+2)";
					}
					for(int i=1;i<=cnt/3;i++){
						cout<<"*(1+1+1)";
					}
					for(int i=cnt1+cnt2+1;i<=n;i++){
						cout<<"*"<<a[i];
					}
				}
				else{
					cout<<"(1+1+1)";
					for(int i=1;i<=cnt/3-1;i++){
						cout<<"*(1+1+1)";
					}
					for(int i=cnt1+cnt2+1;i<=n;i++){
						cout<<"*"<<a[i];
					}
				}
			}
		}
	}
	return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...