比赛时只想到把表达式存起来,再转化成后缀表达式计算的方式,结果MLE了最后一个点
看了题解之后还能这么维护
思路
- 我们可以维护一个的表达式 第一个值即为
如果后面接了一个 ,则变成
如果后面接了一个 ,则变成
如果后面接了一个 ,则变成 ;
如果后面接了一个 ,则变成 。
-----by九峰
代码
// Problem: 吴楚月的表达式 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9984/H // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,b,a) for(int i=(b);i>=(a);i--) #define mst(abc,bca) memset(abc,bca,sizeof abc) #define X first #define Y second #define lowbit(a) (a&(-a)) #define debug(a) cout<<#a<<":"<<a<<"\n" typedef long long ll; typedef pair<int,int> pii; typedef unsigned long long ull; typedef long double ld; const int N=100010; const int INF=0x3f3f3f3f; const int mod=1e9+7; const double eps=1e-6; const double PI=acos(-1.0); struct node{ int ne; char op; }; vector<ll> nums; vector<char> ops; int n,v[N]; ll w[N]; vector<node> g[N]; ll ans[N]; ll fpow(ll a,ll b){ if(mod==1) return 0; ll ans=1%mod; while(b){ if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } void dfs(int u,int fa,ll a,ll b){ for(auto v:g[u]){ if(v.ne==fa) continue; if(v.op=='+') dfs(v.ne,u,(a+b)%mod,w[v.ne]); else if(v.op=='-') dfs(v.ne,u,(a+b)%mod,(-w[v.ne]+mod)%mod); else if(v.op=='*') dfs(v.ne,u,a,(b*w[v.ne])%mod); else if(v.op=='/') dfs(v.ne,u,a,b*fpow(w[v.ne],mod-2)%mod); } ans[u]=(a+b)%mod; } void solve(){ cin>>n; rep(i,1,n) cin>>w[i]; rep(u,2,n){ cin>>v[u]; } rep(u,2,n){ char c;cin>>c; g[u].pb({v[u],c}); g[v[u]].pb({u,c}); } dfs(1,0,0,w[1]); rep(i,1,n) cout<<ans[i]<<" \n"[i==n]; } int main(){ ios::sync_with_stdio(0);cin.tie(0); // debug(fpow(4,mod-2)); // int t;cin>>t;while(t--) solve(); return 0; }