Compressed Bracket Sequence

发表于 更新于 分类于 ，

    给一个长度为 n(1≤n≤1000) 的正整数序列 {cn}(1≤ci≤109)。用该序列一如下方式构造一个括号序列 s：

    1. 开始 c 为空；

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

    求有多少对 ⟨l,r⟩ 使得 sl∼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≤n≤1000) 的正整数序列 {cn},(1≤ci≤109)。用该序列一如下方式构造一个括号序列 s：

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

求有多少对 ⟨l,r⟩ 使得 sl∼r 为合法括号序列。

solution

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

初始时至少有min(ci,ci+1)对括号序列。当ci>ci+1，可以为后续填补ci−ci+1个左括号。

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

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;
}