自动搬运

查看原文

来自洛谷，原作者为

	lfxxx But look at the time!

搬运于2025-08-24 22:32:31，当前版本为作者最后更新于2021-07-15 13:28:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目传送门：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：

$n\le9$，爆搜即可。

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 理解）

如果乘法的负数有奇数个。

跟上面差不多，找一个最大的负数乘上加法的负数和，再加上加法的正数和，最后将剩下的乘法乘上。

代码：

好像有点长

关于我代码中的 vector<int>v4; 。

#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 给了我思路。

如有书写错误，请在下方评论。