各位看一下思路对否
查看原帖
各位看一下思路对否
230808
Zxsoul楼主2021/7/14 19:08

感觉要点就是对于负乘法的处理上,在负乘法中偶数个会产生贡献,奇数个只有绝对值最小的可能产生贡献,把最小的拿出来,其余的又变成偶数个,继续产生贡献,

最小的那个若有负数加,则相乘产生贡献,若没有则与0相乘不产生贡献

求大佬看一下代码,每一个捆绑都有一个点不过

/*
  将所有的数分成 + - * -*
  然后顺序是 - -* + * 
  负数乘可能存在多个,此时应该保留偶数个最大数, 
*/
#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

const int A = 1e5+10;
const int B = 2e6+10;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;

inline int read() {
  char c = getchar();
  int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}
int ja,ji,ch=1,fc=1;
int n;
int flag=0;
int a[B]; 
int cnt;
main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        char c;
        cin>>c; int x=read();
        if (c=='+')
        {
          if (x<0) ji=(ji-x+mod)%mod;
          else ja=ja%mod+x%mod;
        }
        if (c=='*') 
        {
          if (x<0) 
          {
              a[++cnt]=-x;  
          }
          else ch=(ch%mod*x%mod)%mod;
        }
    }
    int ans=0;
    if (cnt%2==0 && !cnt)//偶数个
    {
      for (int i=1;i<=cnt;i++)
      {
        ch=(ch%mod*a[i]%mod)%mod;
      }
    } 
    else if (cnt!=0)//奇数个 
    {
      sort(a+1,a+1+cnt);
      fc=a[1];
      for (int i=2;i<=cnt;i++) ch=ch%mod*a[i]%mod;
    }
    if (ji!=0 && fc!=1) ans=(((ji%mod*fc)%mod+ja%mod+mod)%mod*ch%mod)%mod;
    else ans=((ja*ch%mod-ji+mod)%mod+mod)%mod; 
    printf("%lld",(ans%mod+mod)%mod);
}
/*
3
+ 3
+ 4
* -4
* 4
* 6
*/
2021/7/14 19:08
加载中...