AC链接

比赛的时候并没有过这一题,subtask1和最后一个subtask都其中一个点没有过，结果只有49分 最后看了ix35的题解过了这道题

想法1

一步一步来，中间几个task都好过，全部没有负数的话直接先加起来再乘

想法2

乘数中有负数，但是没加的负数，就讨论一下奇偶，丢掉最小的负数，然后负负得正，转化成想法1求解

想法3

乘数中和加数中都有负数，想法就是让负数和负数抵消成正的，转换成前面两个想法求解

其实我们希望加正数后乘上正数，放大效果最大

同时希望加负数后乘上负数

记M=所有乘数乘积

M>0时和M<0时加减的顺序会变化

于是发现有必要讨论一下乘数中负数的个数的奇偶

如果是奇数个，就方便一些，拿绝对值最小的负乘数去把所有负加数变成正的，变成想法2

想法4

如果负数乘数有偶数个就麻烦一些，我一直没过这两个点

一开始我的想法是有两种策略，一个是丢掉绝对值最小的，用第二小的去抵消负数加数，转换成想法2

或者是直接全乘起来，变成想法1

但是这是错误的

看了solution以后，我发现解决它的方法和想法3类似

目前的M>0，所以先加，加完以后我们就要减了

但是减的条件是M<0，于是把绝对值最小的负数乘数乘到前面，再减，这样能保证最大

最后再乘上所有其他乘数

简单的说就是

先addpos 再乘上multiplyneg[1](排序后的） 再addneg 最后multply other number

#include<bits/stdc++.h>

using namespace std;

long long ans=0,ans1=0,ans2=0;
int n,mutipos[100005],mutineg[100005],addpos[100005],addneg[100005],a=0,b=0,c=0,d=0;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		char op;
		int v;
		cin>>op>>v;
		if((op=='+')&&(v>0))
		{
			a++;
			addpos[a]=v;
		}
		if((op=='+')&&(v<0))
		{
			b++;
			addneg[b]=-v;	
		}
		if((op=='*')&&(v>0))
		{
			c++;
			mutipos[c]=v;
		}
		if((op=='*')&&(v<0))
		{
			d++;
			mutineg[d]=-v;	
		}
	}
	sort(mutineg+1,mutineg+d+1);
	sort(addneg+1,addneg+b+1);
	if((b!=0)&&(d!=0))
	{
		if(d%2==0)
		{
			for(int i=1;i<=a;i++)
			{
				ans+=addpos[i];
				ans%=998244353;
			}
			ans*=-mutineg[1];
			for(int i=1;i<=b;i++)
			{
				ans-=addneg[i];
				ans%=998244353;
			}
			for(int i=1;i<=c;i++)
			{
				ans*=mutipos[i];
				ans%=998244353;
			}
			for(int i=2;i<=d;i++)
			{
				ans*=-mutineg[i];
				ans%=998244353;
			}
			cout<<(ans % 998244353 + 998244353) % 998244353;
		}
		if(d%2==1)
		{
			int num=mutineg[1];
			for(int i=a+1;i<=a+b;i++)
			{
				addpos[i]+=(addneg[i-a]*num);
			}
			a+=b;
			for(int i=c+1;i<c+d;i++)
			{
				mutipos[i]=mutineg[i-c+1];
			}
			c+=d-1;
			for(int i=1;i<=a;i++)
			{
				ans+=addpos[i];
				ans%=998244353;
			}
			for(int i=1;i<=c;i++)
			{
				ans*=mutipos[i];
				ans%=998244353;
			}
			cout<<(ans % 998244353 + 998244353) % 998244353;
		}
	}
	if((b==0)&&(d!=0))
	{
		if(d%2==0)
		{
			for(int i=c+1;i<=c+d;i++)
			{
				mutipos[i]=mutineg[i-c];
			}
			c+=d;
		}
		if(d%2==1)
		{
			for(int i=c+1;i<c+d;i++)
			{
				mutipos[i]=mutineg[i-c+1];
			}
			c+=d-1;
		}
		for(int i=1;i<=a;i++)
		{
			ans+=addpos[i];
			ans%=998244353;
		}
		for(int i=1;i<=c;i++)
		{
			ans*=mutipos[i];
			ans%=998244353;
		}
		cout<<(ans % 998244353 + 998244353) % 998244353;
	}
	if((b!=0)&&(d==0))
	{
		for(int i=1;i<=a;i++)
		{
			ans+=addpos[i];
			ans%=998244353;
		}
		for(int i=1;i<=c;i++)
		{
			ans*=mutipos[i];
			ans%=998244353;
		}
		for(int i=1;i<=b;i++)
		{
			ans-=addneg[i];
			ans%=998244353;
		}
		cout<<(ans % 998244353 + 998244353) % 998244353;
	}
	if((b==0)&&(d==0))
	{
		for(int i=1;i<=a;i++)
		{
			ans+=addpos[i];
			ans%=998244353;
		}
		for(int i=1;i<=c;i++)
		{
			ans*=mutipos[i];
			ans%=998244353;
		}
		cout<<(ans % 998244353 + 998244353) % 998244353;
	}
}