专栏文章

在银河中孤独摇摆

IIniaugoty
P14060题解参与者 11已保存评论 16

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
16 条
当前快照
1 份
快照标识符
@mintmt3u
此快照首次捕获于
2025/12/02 08:09
3 个月前
此快照最后确认于
2025/12/02 08:09
3 个月前
查看原文
钦定首字符为 1\texttt 1。操作过程可以看成，对于每一个 0\texttt 0，选择前面的一个 1\texttt 1 配对上，（当然可能选择不到），然后同时把他们删除。如果每一个 0\texttt 0 都能成功配对，意味着开头始终不会变成 0\texttt 0，这个串自然是合法的。
考虑把 1\texttt 1 看成 +1+1，把 0\texttt 0 看成 −1-1，则串合法的充要条件是任意前缀和非负，即对于 ∀k∈[1,n]\forall k \in [1, n]，∑i=1kai≥0\sum_{i=1}^k a_i \ge 0。
这样枚举每一个子串直接 check，有 O(n2)O(n^2) 和 O(n3)O(n^3) 的做法。
令原串的前缀和为 ss。考虑固定左端点 ll，[l,r][l, r] 合法即 ∀i∈[l,r]\forall i \in [l, r]，si≥sl−1s_i \ge s_{l-1}。考虑单调栈，对于每一个 l−1l-1，求出最小的 r′r' 使得 sr′<sl−1s_{r'} < s_{l-1}，则 ∀r∈[l,r′)\forall r \in [l, r') 的 rr 都是合法右端点。
这样有时间复杂度 O(n)O(n) 的做法。
CPP
#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;
}

评论

共 16 条评论，欢迎与作者交流。

正在加载评论...