珍珠帝王蟹

题目背景

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

题目描述

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

帝王蟹有一个初始为 0 的强度值,每个宝石有属性 op 和 v,表示:

若 op 为 +,则镶嵌后帝王蟹的强度值将会加上 v;

若 op 为 *,则镶嵌后帝王蟹的强度值将会乘上 v。

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

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

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

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

输入格式

第一行,一个整数 n,表示宝石数量。

接下来 n 行,每行有用空格隔开的一个字符 op 和一个整数 v,描述一个宝石。

输出格式

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

输入输出样例

输入 #1 复制
3
+ -3
+ 4
* -4
输出 #1 复制
16
输入 #2 复制
3
+ -3
+ -4
* 4
输出 #2 复制
998244346

【数据范围】

本题采用捆绑测试。

对于全部测试数据:1≤n≤10{5},2≤∣v∣≤10{6}
Subtask 1(26 points):n≤9,∣v∣≤5。
Subtask 2(22 points):v > 0。
Subtask 3(12 points):保证当 op为 * 时 v > 0
Subtask 4(15 points):保证当 op 为 + 时 v > 0
Subtask 5(25 points):无特殊限制。

题目分析

考虑分别分析子任务

subtask2:v>0

v>0时,可以证明直接加上所有+数在乘所有*数

subtask3:op=‘*’时,v>0

考虑如果存在(a-b)*c,负数乘c的负面贡献远比单独的减法大,即当v>=2时,(a-b)*c<a*c-b

所以直接统计正数sum1和正数乘积mul1,负数和sum2;答案即sum1*mul1-sum2

subtask4:op=‘+’时,v>0

1.如果乘法的负数数量为偶数,因为负负得正,同subtask2

2.如果乘法数量为奇数,舍弃绝对值最小的负数(最开始用0乘),然后因为偶数个负数同subtask2

subtask5:

相比起前面的情况,考虑怎么利用乘法负数让加法负数贡献为正

根据前面的分析得出:乘法可以带来的贡献的绝对值比不乘要多

如果乘法的负数有偶数个:

1.无乘法负数同上

2.有乘法负数:最大的负数乘上加法的正数和,然后再加上加法的负数和,最后乘上所有乘法

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

最大的负数乘上加法的负数和,再加上加法的正数和,最后将剩下的乘法乘上

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
//sum1是+正数和,sum2是+负数和
//mul1是*正数积,mul2是*除Max外负数积,Max是最大负数数组下标
//arr是保存*负数的数组,用于求积时除去Max
int n;
ll sum1=0,sum2=0,mul1=1,mul2=1;
int Max=0,cnt=0;
int Mod=998244353;
ll arr[100005];
int main(){
    char ch;
    ll x;
    //禁用cin的ios和stdio同步从而加速cin
    ios::sync_with_stdio(false);
    cin>>n;
    arr[0]=1;//注意默认乘积绝对值最小值不能为0
    for (int i=1;i<=n;i++){
        cin>>ch>>x;
        if (ch=='+'){
            if (x>0) sum1=(sum1+x)%Mod;
            else sum2=(sum2+x)%Mod;
        }else{
            if (x>0) mul1=mul1*x%Mod;
            else{
                arr[++cnt]=x;
                if (cnt==1) Max=1;
                else if (x>arr[Max]) Max=cnt;
            }
        }
    }
    for(int i=1;i<=cnt;i++){
        if (i!=Max) mul2=mul2*arr[i]%Mod;
    }
    Max=arr[Max];
    //cout<<sum1<<" "<<sum2<<" "<<mul1<<" "<<mul2<<" "<<Max<<endl;
    if (cnt%2==0){
        if (cnt==0)
            cout<<(sum1*mul1%Mod+sum2+Mod)%Mod<<endl;
        else cout<<(sum1*Max%Mod+sum2)%Mod*mul1%Mod*mul2%Mod<<endl;
    }else
        cout<<(sum2*Max%Mod+sum1)%Mod*mul1%Mod*mul2%Mod<<endl;
}
原文地址:https://www.cnblogs.com/Y-E-T-I/p/15128875.html