题目链接：https://codeforces.com/contest/1373/problem/C
给出一个只含有 $+$ 或 $-$ 的字符串 $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$ 的值。
$res$ 即所有位置被访问次数的总和。
模拟伪代码，计算走到每个位置时的值，如果当前位置的值比之前所有位置的都要小，则此时 $cur < 0$，意味着当前位置及之前的字符都要再走一遍，而且下一次走到当前位置时 $cur = 0$ 。
或许更好理解的差分写法。
#include <bits/stdc++.h> using namespace std; void solve() { string s; cin >> s; int n = s.size(); int cnt[n] = {}; //cnt[i] 为位置 i 被访问的次数 cnt[0] = 1; int mi = 0, now = 0; for (int i = 0; i < n; i++) { if (s[i] == ‘+‘) ++now; else --now; if (now < mi) { mi = now; ++cnt[0]; --cnt[i + 1]; } } for (int i = 1; i < n; i++) cnt[i] += cnt[i - 1]; cout << accumulate(cnt, cnt + n, 0LL) << "\n"; } int main() { int t; cin >> t; while (t--) solve(); }
代码一的简化版。
#include <bits/stdc++.h> using ll = long long; using namespace std; void solve() { string s; cin >> s; ll ans = s.size(); int mi = 0, now = 0; for (int i = 0; i < s.size(); i++) { if (s[i] == ‘+‘) ++now; else --now; if (now < mi) { mi = now; ans += i + 1; } } cout << ans << "\n"; } int main() { int t; cin >> t; while (t--) solve(); }
Educational Codeforces Round 90 (Rated for Div. 2) C. Pluses and Minuses（差分）
原文：https://www.cnblogs.com/Kanoon/p/13196870.html