打卡信奥刷题（3154）用C++实现信奥题 P7725 珍珠帝王蟹（Crab King）-开发者社区

P7725 珍珠帝王蟹（Crab King）

题目背景

在一次航程中，你偶然发现了被一片礁石环绕的帝王蟹，被月岛能量侵蚀的它又与月光有着怎样的联系呢？似乎只有击败它才能见分晓。

题目描述

帝王蟹可以通过镶嵌宝石触发战斗，不同的宝石效果不同，但奇特的是，镶嵌宝石的顺序有时也会影响它的强度。

帝王蟹有一个初始为000的强度值，每个宝石有属性opopop和vvv，表示：

若opopop为+，则镶嵌后帝王蟹的强度值将会加上vvv；
若opopop为*，则镶嵌后帝王蟹的强度值将会乘上vvv。

由于宝石的效果十分奇异，所以vvv可能是负数。

作为一个有挑战精神的冒险者，你希望采取某种镶嵌方式，将每个宝石都镶嵌恰好一遍，且使得帝王蟹的强度值最大。

你只需要输出最大的强度值对998244353998244353998244353取模的结果，注意这是一个[0,998244353)[0, 998244353)[0,998244353)中的数。

也就是说，如果答案为ans，按照 C++ 语法，你需要输出(ans % P + P) % P，其中P = 998244353。

输入格式

第一行，一个整数nnn，表示宝石数量。

接下来nnn行，每行有用空格隔开的一个字符opopop和一个整数vvv，描述一个宝石。

输出格式

输出一行一个整数，表示最大的强度值对998244353998244353998244353取模的结果。

输入输出样例 #1

输入 #1

3 + -3 + 4 * -4

输出 #1

输入输出样例 #2

输入 #2

3 + -3 + -4 * 4

输出 #2

998244346

说明/提示

【样例 1 解释】

按照输入顺序以1,2,31, 2, 31,2,3标记每个宝石，所有可能的镶嵌顺序如下：

1→2→31\to 2\to 31→2→3：x=((0+−3)+4)×−4=−4x = ((0 + {\color{red}{-3}}) + {\color{red}{4}}) \times {\color{red}{-4}} = -4x=((0+−3)+4)×−4=−4；

1→3→21\to 3\to 21→3→2：x=((0+−3)×−4)+4=16x = ((0 + {\color{red}{-3}}) \times {\color{red}{-4}}) + {\color{red}{4}} = 16x=((0+−3)×−4)+4=16；

2→1→32\to 1\to 32→1→3：x=((0+4)+−3)×−4=−4x = ((0 + {\color{red}{4}}) + {\color{red}{-3}}) \times {\color{red}{-4}} = -4x=((0+4)+−3)×−4=−4；

2→3→12\to 3\to 12→3→1：x=((0+4)×−4)+−3=−19x = ((0 + {\color{red}{4}}) \times {\color{red}{-4}}) + {\color{red}{-3}} = -19x=((0+4)×−4)+−3=−19；

3→1→23\to 1\to 23→1→2：x=((0×−4)+−3)+4=1x = ((0 \times {\color{red}{-4}}) + {\color{red}{-3}}) + {\color{red}{4}} = 1x=((0×−4)+−3)+4=1；

3→2→13\to 2\to 13→2→1：x=((0×−4)+4)+−3=1x = ((0 \times {\color{red}{-4}}) + {\color{red}{4}}) + {\color{red}{-3}} = 1x=((0×−4)+4)+−3=1。

因此，强度值的最大值为161616，对998244353998244353998244353取模后为161616。

【样例 2 解释】

按照输入顺序以1,2,31, 2, 31,2,3标记每个宝石，所有可能的镶嵌顺序如下：

1→2→31\to 2\to 31→2→3：x=((0+−3)+−4)×4=−28x = ((0 + {\color{red}{-3}}) + {\color{red}{-4}}) \times {\color{red}{4}} = -28x=((0+−3)+−4)×4=−28；

1→3→21\to 3\to 21→3→2：x=((0+−3)×4)+−4=−16x = ((0 + {\color{red}{-3}}) \times {\color{red}{4}}) + {\color{red}{-4}} = -16x=((0+−3)×4)+−4=−16；

2→1→32\to 1\to 32→1→3：x=((0+−4)+−3)×4=−28x = ((0 + {\color{red}{-4}}) + {\color{red}{-3}}) \times {\color{red}{4}} = -28x=((0+−4)+−3)×4=−28；

2→3→12\to 3\to 12→3→1：x=((0+−4)×4)+−3=−19x = ((0 + {\color{red}{-4}}) \times {\color{red}{4}}) + {\color{red}{-3}} = -19x=((0+−4)×4)+−3=−19；

3→1→23\to 1\to 23→1→2：x=((0×4)+−3)+−4=−7x = ((0 \times {\color{red}{4}}) + {\color{red}{-3}}) + {\color{red}{-4}} = -7x=((0×4)+−3)+−4=−7；

3→2→13\to 2\to 13→2→1：x=((0×4)+−4)+−3=−7x = ((0 \times {\color{red}{4}}) + {\color{red}{-4}}) + {\color{red}{-3}} = -7x=((0×4)+−4)+−3=−7。

因此，强度值的最大值为−7-7−7，对998244353998244353998244353取模后为998244346998244346998244346。

【数据范围】

本题采用捆绑测试。

对于全部测试数据：1≤n≤1051 \le n \le {10}^51≤n≤105，2≤∣v∣≤1062 \le |v| \le {10}^62≤∣v∣≤106。

Subtask 1（26 points）：n≤9n \le 9n≤9，∣v∣≤5|v| \le 5∣v∣≤5。
Subtask 2（22 points）：v>0v > 0v>0。
Subtask 3（12 points）：保证当opopop为*时v>0v > 0v>0。
Subtask 4（15 points）：保证当opopop为+时v>0v > 0v>0。
Subtask 5（25 points）：无特殊限制。

C++实现

#include<iostream>#include<vector>#definelllonglongusingnamespacestd;constintmod=998244353;ll s1,s2,s3=1,s4=1;intmax4=0;vector<int>v4;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);//cin，cout加速intn;cin>>n;for(inti=1;i<=n;i++){charop;intv;cin>>op>>v;if(op=='+')if(v>0)s1=(s1+v)%mod;elses2=(s2+v)%mod;elseif(v>0)s3=s3*v%mod;elsev4.push_back(v);}if(!v4.empty()){for(inti=1;i<v4.size();i++)if(v4[i]>v4[max4])max4=i;for(inti=0;i<v4.size();i++)if(i!=max4)s4=s4*v4[i]%mod;max4=v4[max4];}//找最大值elsemax4=1;if(!(v4.size()&1))if(v4.empty())cout<<(s1*s3%mod+s2+mod)%mod<<endl;elsecout<<(s1*max4%mod+s2)%mod*s3%mod*s4%mod<<endl;elsecout<<(s2*max4%mod+s1)*s4%mod*s3%mod<<endl;return0;}