题目描述
王老师脑袋一拍，定义了乘加运算！
他定义 a∗bc=(a+b)×c 。
而且他觉得用括号来规定运算的先后顺序太麻烦了，他给乘加运算定义了一个权值的系数（为乘加运算的下标），权值大的乘加运算先进行。
例如下面的表达式：
=====9 ∗34 9 ∗12 1 ∗23 6 ∗41 29 ∗34 9 ∗12 1 ∗23 (6+1)×2 因为∗41权值最大(4)，所以先运算(9+4)×9 ∗12 1 ∗23 14117 ∗12 (1+3)×14(117+2)×566664
现在王老师 给你一个只含有乘加运算的表达式，希望你能帮他求出最后的值。
数据范围
对于 100% 的数据，保证：1≤n≤105,0≤ai,ci≤109,−109≤bi≤109。
| 测试点编号 | 数据范围 | 特殊性质 |
|---|---|---|
| 1∼3 | n≤100 | 无 |
| 4∼8 | n≤1000 | 无 |
| 9 | 无限制 | ai=0 |
| 10∼14 | 无限制 | bi=0 |
| 15∼20 | 无限制 | 无 |
根据题目可知，我们需要使用一种能够快速插入删除元素的容器，所以不难想到用链表解决，其次数据量非常大，需要开long long
代码：
#include <bits/stdc++.h>using namespace std;
#define int long long
int n,pr[100005],ne[100005],id[100005],a[100005];
struct no{
int x,y;
}b[100005];
bool tmp(int x,int y){
return b[x].y>b[y].y;
}
signed main(){
freopen("mulsum.in","r",stdin);
freopen("mulsum.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<n;i++)cin>>b[i].x;
for(int i=1;i<n;i++)cin>>b[i].y,id[i]=i,pr[i]=i-1,ne[i]=i+1;
sort(id+1,id+n+1,tmp);
for(int i=1;i<n;i++){
int x=id[i];
a[ne[x]]=(a[x]+b[x].x)*a[ne[x]];
pr[ne[x]]=pr[x],ne[pr[x]]=ne[x];
}
cout<<a[n];
return 0;
} 总结：在赛场上我其实想到了链表做法，可不会实现，链表的基础操作应该更加熟练。 标签：赛道,100005,int,pr,乘加,ne,T1,2024,id From： https://www.cnblogs.com/qianqian2022/p/18391689