题目链接：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
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
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();
}