Educational Codeforces Round 90 (Rated for Div. 2) C. Pluses and Minuses (1300)

    技术2022-07-11  112

    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; }
    Processed: 0.011, SQL: 9