打卡信奥刷题（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输入 #13 -3 4 * -4输出 #116输入输出样例 #2输入 #23 -3 -4 * 4输出 #2998244346说明/提示【样例 1 解释】按照输入顺序以1,2,31, 2, 31,2,3标记每个宝石所有可能的镶嵌顺序如下1→2→31\to 2\to 31→2→3x((0−3)4)×−4−4x ((0 {\color{red}{-3}}) {\color{red}{4}}) \times {\color{red}{-4}} -4x((0−3)4)×−4−41→3→21\to 3\to 21→3→2x((0−3)×−4)416x ((0 {\color{red}{-3}}) \times {\color{red}{-4}}) {\color{red}{4}} 16x((0−3)×−4)4162→1→32\to 1\to 32→1→3x((04)−3)×−4−4x ((0 {\color{red}{4}}) {\color{red}{-3}}) \times {\color{red}{-4}} -4x((04)−3)×−4−42→3→12\to 3\to 12→3→1x((04)×−4)−3−19x ((0 {\color{red}{4}}) \times {\color{red}{-4}}) {\color{red}{-3}} -19x((04)×−4)−3−193→1→23\to 1\to 23→1→2x((0×−4)−3)41x ((0 \times {\color{red}{-4}}) {\color{red}{-3}}) {\color{red}{4}} 1x((0×−4)−3)413→2→13\to 2\to 13→2→1x((0×−4)4)−31x ((0 \times {\color{red}{-4}}) {\color{red}{4}}) {\color{red}{-3}} 1x((0×−4)4)−31。因此强度值的最大值为161616对998244353998244353998244353取模后为161616。【样例 2 解释】按照输入顺序以1,2,31, 2, 31,2,3标记每个宝石所有可能的镶嵌顺序如下1→2→31\to 2\to 31→2→3x((0−3)−4)×4−28x ((0 {\color{red}{-3}}) {\color{red}{-4}}) \times {\color{red}{4}} -28x((0−3)−4)×4−281→3→21\to 3\to 21→3→2x((0−3)×4)−4−16x ((0 {\color{red}{-3}}) \times {\color{red}{4}}) {\color{red}{-4}} -16x((0−3)×4)−4−162→1→32\to 1\to 32→1→3x((0−4)−3)×4−28x ((0 {\color{red}{-4}}) {\color{red}{-3}}) \times {\color{red}{4}} -28x((0−4)−3)×4−282→3→12\to 3\to 12→3→1x((0−4)×4)−3−19x ((0 {\color{red}{-4}}) \times {\color{red}{4}}) {\color{red}{-3}} -19x((0−4)×4)−3−193→1→23\to 1\to 23→1→2x((0×4)−3)−4−7x ((0 \times {\color{red}{4}}) {\color{red}{-3}}) {\color{red}{-4}} -7x((0×4)−3)−4−73→2→13\to 2\to 13→2→1x((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≤1052≤∣v∣≤1062 \le |v| \le {10}^62≤∣v∣≤106。Subtask 126 pointsn≤9n \le 9n≤9∣v∣≤5|v| \le 5∣v∣≤5。Subtask 222 pointsv0v 0v0。Subtask 312 points保证当opopop为*时v0v 0v0。Subtask 415 points保证当opopop为时v0v 0v0。Subtask 525 points无特殊限制。C实现#includeiostream#includevector#definelllonglongusingnamespacestd;constintmod998244353;ll s1,s2,s31,s41;intmax40;vectorintv4;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);//cincout加速intn;cinn;for(inti1;in;i){charop;intv;cinopv;if(op)if(v0)s1(s1v)%mod;elses2(s2v)%mod;elseif(v0)s3s3*v%mod;elsev4.push_back(v);}if(!v4.empty()){for(inti1;iv4.size();i)if(v4[i]v4[max4])max4i;for(inti0;iv4.size();i)if(i!max4)s4s4*v4[i]%mod;max4v4[max4];}//找最大值elsemax41;if(!(v4.size()1))if(v4.empty())cout(s1*s3%mods2mod)%modendl;elsecout(s1*max4%mods2)%mod*s3%mod*s4%modendl;elsecout(s2*max4%mods1)*s4%mod*s3%modendl;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容