C. Pluses and Minuses 题意: 给一个字符串s,有如下代码:
res = 0 for init = 0 to inf cur = init ok = true for i = 1 to |s| res = res + 1 if s[i] == '+' cur = cur + 1 else cur = cur - 1 if cur < 0 ok = false break if ok break求res最后的值
思路: 跑一遍循环,依次找前缀和为 -1、-2、-3、……时的情况,答案要加上当时的结点值,最后再加上s的长度就行了 (其实就是把题目给的代码优化一下)
代码附:
#pragma GCC optimize("Ofast","inline","-ffast-math") #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<bits/stdc++.h> #define int long long using namespace std; const int N = 2e5+10; signed main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin>>t; string ss; while(t--) { cin>>ss; int now=-1,ans=0,sum=0; for(int i=0;ss[i];++i) { if(ss[i]=='-')sum--; else sum++; if(sum==now) { now--; ans+=i+1; } }ans+=ss.length(); cout<<ans<<endl; } return 0; }