题解：P13707 [NWERC 2023] Higher Arithmetic

LinkCatTree · 2025-11-17 19:16:37 · 题解

提供一种比较简洁的做法捏。

我们发现 1 非常烦啊，大力分讨一下。首先如果 1 和 2 都有剩余，那么组成 (1+2) 显然是优的。于是我们处理完了所有的 1 或所有的 2，如果剩余的是 1 那就尽量三个一组 (1+1+1)，剩余的小心分讨一下即可。

快快乐乐找 coner case，我们发现 1 恰比 2 多一个的时候显然 (1+2) \times \cdots \times (1+2) \times (1+1) \times 2 显然是要比 (1+2) \times \cdots (1+2) 剩下一个 1 更优的，特判即可。

const int N=1e5+5;
int n,a[N],ch;

int main() {
    for(int i=(scanf("%d",&n),1);i<=n;i++) scanf("%d",&a[i]);
    if(n==1) return printf("%d\n",a[1]),0;
    sort(a+1,a+1+n);
    int d1=upper_bound(a+1,a+1+n,1)-a-1,p1=d1;
    int d2=upper_bound(a+1,a+1+n,2)-a-1,p2=d2;
    auto pt=[](int& ch)->void {(ch?printf("*"):ch=1);};
    for(;p2>d1&&p1>0;p1--,p2--)
        if(p2>d1+1||p1!=2) pt(ch),printf("(2+1)");
        else pt(ch),printf("(2+1+1)"),--p1;
    for(;p2>d1;--p2) pt(ch),printf("2");
    for(;p1>4;p1-=3) pt(ch),printf("(1+1+1)");
    if(p1==4) pt(ch),printf("(1+1)*(1+1)");
    if(p1==3) pt(ch),printf("(1+1+1)");
    if(p1==2) pt(ch),printf("(1+1)");
    if(p1==1) pt(ch),printf("(1+%d)",a[++d2]);
    for(++d2;d2<=n;d2++) pt(ch),printf("%d",a[d2]);
    return printf("\n"),0;
}