在银河中孤独摇摆

Iniaugoty · 2025-09-22 14:33:07 · 题解

钦定首字符为 \texttt 1。操作过程可以看成，对于每一个 \texttt 0，选择前面的一个 \texttt 1 配对上，（当然可能选择不到），然后同时把他们删除。如果每一个 \texttt 0 都能成功配对，意味着开头始终不会变成 \texttt 0，这个串自然是合法的。

考虑把 \texttt 1 看成 +1，把 \texttt 0 看成 -1，则串合法的充要条件是任意前缀和非负，即对于 \forall k \in [1, n]，\sum_{i=1}^k a_i \ge 0。

这样枚举每一个子串直接 check，有 O(n^2) 和 O(n^3) 的做法。

令原串的前缀和为 s。考虑固定左端点 l，[l, r] 合法即 \forall i \in [l, r]，s_i \ge s_{l-1}。考虑单调栈，对于每一个 l-1，求出最小的 r' 使得 s_{r'} < s_{l-1}，则 \forall r \in [l, r') 的 r 都是合法右端点。

这样有时间复杂度 O(n) 的做法。

#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> vec;
typedef array<int, 2> arr;
const int N = 1e7 + 5;

int n, a[N], s[N], r[N], st[N], tp; char c[N]; LL ans;

void Solve() {
  F(i, 1, n + 1) {
    while (tp > 0 && s[st[tp]] < s[i])
      r[st[tp--]] = i;
    st[++tp] = i;
  }
  while (tp) r[st[tp--]] = n + 2;
  F(i, 1, n) ans += r[i] - i - 1;
}

void mian() {
  cin >> c, n = strlen(c), ans = 0;
  F(i, 1, n) a[i] = c[i - 1] - '0';
  s[n + 1] = 0;
  dF(i, n, 1) s[i] = s[i + 1] + (a[i] ? 1 : -1);
  Solve();
  dF(i, n, 1) s[i] = s[i + 1] + (a[i] ? -1 : 1);
  Solve();
  cout << ans << "\n";
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _; cin >> _; while (_--) mian();
  return 0;
}