Compressed Bracket Sequence

发表于 更新于 分类于 ，

    给一个长度为 $n\,(1\le n\le 1000)$ 的正整数序列 $\left\lbrace c_n\right\rbrace \,(1\le c_i\le 10^9)$。用该序列一如下方式构造一个括号序列 $s$：

    1. 开始 $c$ 为空；

    2. 对 $i$ 从 $1$ 到 $n$ 依次遍历，若 $i$ 为奇数，则在 $s$ 后插入 $c_i$ 个 '('，否则插入 $c_i$ 个 ')'。

    求有多少对 $\left<l,r\right>$ 使得 $s_{l\sim r}$ 为合法括号序列。

Compressed Bracket Sequence

Created by LXC on Mon Mar 4 15:55:52 2024

https://codeforces.com/problemset/problem/1556/C

ranting: 1800

tag: brute force, implementation

problem

给一个长度为 $n,(1\le n\le 1000)$ 的正整数序列 $\left\lbrace c_n\right\rbrace ,(1\le c_i\le 10^9)$。用该序列一如下方式构造一个括号序列 $s$：

  1. 开始 $c$ 为空；
  2. 对 $i$ 从 $1$ 到 $n$ 依次遍历，若 $i$ 为奇数，则在 $s$ 后插入 $c_i$ 个 '('，否则插入 $c_i$ 个 ')'。

求有多少对 $\left<l,r\right>$ 使得 $s_{l\sim r}$ 为合法括号序列。

solution

考虑以$c_i$作为左端点有多少合法的括号序列。

初始时至少有$min(c_i, c_{i+1})$对括号序列。当$c_i > c_{i+1}$，可以为后续填补$c_i-c_{i+1}$个左括号。

什么时候需要填补？$c_{j} < c_{j+1}$时，需要填补$c_{j+1}-c_{j}$个。可过程中存在$c_{j}>c_{j+1}$，也可以为后续填补左括号。所以需要维护一个左括号前缀和，当前真正缺的左括号数目还需要加上之前的左括号，然后再用$c_i > c_{i+1}$的左括号填补才能保证是以$c_i$作为开端的子串。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (ll& i:a) cin >> i;
    ll ans = 0;
    for (int i=0; i+1<n; i+=2) {
        ll res = a[i]-a[i+1];
        ans += min(a[i+1], a[i]);
        if (res < 0) continue;
        ll req = 0; 
        for (int j=i+3; j<n; j+=2) {
            req -= a[j-1] - a[j];
            if (req >= 0) {
                ans += min(res, req)+1;
                res -= req;
                req = 0;
            }
            if (res<0) break;
        }
        // cout << i << " " << ans << endl;
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}