题解：P13707 [NWERC 2023] Higher Arithmetic

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

我们发现

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

更优的，特判即可。

CPP

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;
}

题解：P13707 [NWERC 2023] Higher Arithmetic

文章操作

相关推荐

评论

题解：P13707 [NWERC 2023] Higher Arithmetic