P7725 珍珠帝王蟹（Crab King）
Bb1t
·
·
题解
题目传送门：P7725 珍珠帝王蟹（Crab King）
UPD：
2021-07-21：稍微修改了下代码并增加了一下关于代码的内容。
2021-08-04：再次稍微修改题解。
2021-08-25：又一次稍微修改题解。
前记：
月赛时被这题恶心到了，果然还是太蒟了于是在月赛后好好研究了这题，就有了这篇题解。
题意：
初始贡献为 0 ，给你 n 个字符 op 和整数 v（v 可以为负数），（每次给定 1 组 op 和 v）并且你要进行 n 次操作。
每次操作你需要选一组 op 和 v，并且每组都要选 1 次。
-
若该 op 为 + ，则贡献加 v ；
-
若该 op 为 * ，则贡献乘 v 。
请安排选的顺序使贡献最大，输出贡献对 998244353 取模的值。
思路：
不难看出该题是贪心，但贪心策略一眼看不出来，于是按 Subtask 来思考。
Subtask 1：
### Subtask 2：
$v>0$。
不难想到先加上所有数再乘上所有数。（证明略）~~这么明显应该不用证吧~~
### Subtask 3：
保证当 $op$ 为 `*` 时 $v>0$。
由于乘法只有正数，所以如果负数被乘了，贡献会大大减少，所以只让正数乘，然后加上负数。
### Subtask 4：
保证当 $op$ 为 `+` 时 $v>0$。
这时如果**乘法的负数有偶数个，那跟 Subtask 2 没有区别**（负负得正）。
如果**乘法的负数有奇数个呢？**，我们可以舍弃**绝对值最小**的负数（即**最大**的负数），接下来又跟 Subtask 2 没有区别。
### Subtask 5：
经过前面的思考，我们看出：**乘法可以带来的贡献的绝对值比不乘要多。**（$|v|\ge2$）此时我们再思考最终的贪心策略。
优先考虑乘法。
#### 如果乘法的负数有偶数个。
1. 无乘法负数
同 Subtask 3。
2. 有乘法负数
尽可能让多的数乘，怎么将**正数和负数都能乘上去**且都是**正贡献**呢？
**负负得正！**
可以找一个**最大的负数乘上加法的正数和**，然后再**加上加法的负数和**，最后**乘上所有乘法**。（这段话可能难理解，可以结合[讨论区的那个 Hack ](https://www.luogu.com.cn/discuss/show/328252)理解）
#### 如果乘法的负数有奇数个。
跟上面差不多，找一个**最大的负数乘上加法的负数和**，再**加上加法的正数和**，最后**将剩下的乘法乘上**。
## 代码：
~~好像有点长~~
关于我代码中的 [`vector<int>v4;`](https://blog.csdn.net/sss_0916/article/details/90380644) 。
```cpp
#include<iostream>
#include<vector>
#define ll long long
using namespace std;
const int mod=998244353;
ll s1,s2,s3=1,s4=1;
int max4=0;
vector<int>v4;
//s1表示加法的正数，s2表示减法的正数，s3表示乘法的正数，s4表示乘法的负数。v4是记录s4的数的，因为要记录最大值。
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);//cin，cout加速
int n;
cin>>n;
for(int i=1;i<=n;i++){
char op;
int v;
cin>>op>>v;
if(op=='+')
if(v>0)
s1=(s1+v)%mod;
else
s2=(s2+v)%mod;
else
if(v>0)
s3=s3*v%mod;
else
v4.push_back(v);
}
if(!v4.empty()){
for(int i=1;i<v4.size();i++)
if(v4[i]>v4[max4])
max4=i;
for(int i=0;i<v4.size();i++)
if(i!=max4)
s4=s4*v4[i]%mod;
max4=v4[max4];
}//找最大值
else
max4=1;
if(!(v4.size()&1))
if(v4.empty())
cout<<(s1*s3%mod+s2+mod)%mod<<endl;
else
cout<<(s1*max4%mod+s2)%mod*s3%mod*s4%mod<<endl;
else
cout<<(s2*max4%mod+s1)*s4%mod*s3%mod<<endl;
return 0;
}
```
## 后记：
感谢[这个讨论中的 Hack ](https://www.luogu.com.cn/discuss/show/328252)给了我思路。
如有书写错误，请在下方评论。