数据结构

sccc_ · 2025-10-23 17:48:14 · 个人记录

P14172 【MX-X23-T2】括号串

错因：思路细节错误，有可能虽然相邻两个是 )(，但是可能原本就是匹配的，改了之后反倒不匹配了。

思路：当遇到 ( 时，将他压进栈，否则，若栈内还有未匹配的括号，则 stk.pop()，再否则，判断是否用过一次机会，是的话就无解，否则使用一次机会。

#include <bits/stdc++.h>

using namespace std;

int t, n;
string s;

void work() {
    cin >> n >> s;
    bool f = 0;
    stack<char> stk;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(')
            stk.push(s[i]);
        else if (!stk.empty() && stk.top() == '(')
            stk.pop();
        else if (f) {
            cout << "No\n";
            return;
        } else {
            f = 1;
            stk.push(s[i + 1]);
            s[i + 1] = s[i];
        }
    }

    if (stk.empty()) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }   
}

signed main() {
    cin >> t;
    while (t--) {
        work();
    }
    return 0;
} 

P1020 [NOIP 1999 提高组] 导弹拦截

第一问：求最长不上升子序列长度。

第二问：求要多少个不上升子序列才能覆盖原数组——即最长上升子序列的长度。

对于 dp，O(n^2) 的方法只有一半分数，考虑树状数组优化 dp。

树状数组存储比 x 小的最大 dp 值。

对于第一问，我们可以把它当成最长后缀不下降子序列。

状态：dp_i 表示后面 i 个数的最长后缀不下降子序列长度。

答案：\max(dp_i)。

状态转移方程：dp_i = query(a_i) + 1。

初始化：dp_i = 1。

对于第二问，我们可以把它当成最长上升子序列。

状态：dp_i 表示前 i 个数的最长上升子序列长度。

答案：\max(dp_i)。

状态转移方程：dp_i = query(a_i - 1) + 1，因为是严格上升。

初始化：dp_i = 1。

#include <bits/stdc++.h>

using namespace std;

int dp[100005], a[100005], tr[400005];

int lowbit(int x) {
    return x & (-x);
}

void modify(int x, int val) {
    while (x <= 5e4) {
        tr[x] = max(tr[x], val);
        x += lowbit(x);
    }
}

int query(int x) {
    int maxn = 0;
    while (x) {
        maxn = max(maxn, tr[x]);
        x -= lowbit(x);
    }
    return maxn;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n = 1;
    for (; cin >> a[n]; n++) {
        dp[n] = 1;
    }
    n--;
    for (int i = n; i >= 1; i--) {
        dp[i] = query(a[i]) + 1;
        modify(a[i], dp[i]);    
    }
    cout << *max_element(dp + 1, dp + 1 + n) << '\n';
    memset (tr, 0, sizeof tr);
    memset (dp, 0, sizeof dp);
    for (int i = 1; i <= n; i++) {
        dp[i] = query(a[i] - 1) + 1;
        modify(a[i], dp[i]);    
    }
    cout << *max_element(dp + 1, dp + 1 + n);
    return 0;
}

CF547B Mike and Feet

若用暴力枚举 + 数据结构会 T，考虑单调栈 + 单调性优化。

1. 考虑每个 a_i 成为最小值的贡献；
2. 对于某个最小值 a_i，若可以在长度为 len 的区间内成为最小值，那么在长度在 [1,len] 的所有长度的区间都可以成为最小值，从而参与对于长度区间的最大值竞争；
3. 预处理 a_i 成为最小值的最长区间，显然用单调栈维护；
4. 维护 l_i, r_i 表示 a_i 成为最小值的最小下标和最大下标；
6. 倒序枚举区间长度 len 从 n 到 1，ans_{len} = \max(ans_{len}, ans_{len + 1})。

#include <bits/stdc++.h>

using namespace std;

int n, a[2000005], r[200005], l[200005], ans[2000005];
stack<int> s;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        while (!s.empty() && a[i] < a[s.top()]) {
            r[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
    while (!s.empty()) {
        r[s.top()] = n + 1;
        s.pop();
    }
    for (int i = n; i >= 1; i--) {
        while (!s.empty() && a[i] < a[s.top()]) {
            l[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
    while (!s.empty()) {
        l[s.top()] = 0;
        s.pop();
    }
    for (int i = 1; i <= n; i++) {
        ans[r[i] - 1 - (l[i] + 1) + 1] = max(ans[r[i] - 1 - (l[i] + 1) + 1], a[i]);
    }
    for (int i = n; i >= 1; i--) {
        ans[i] = max(ans[i], ans[i + 1]);
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }
    return 0;
}

P12347 [蓝桥杯 2025 省 A 第二场] 栈与乘积

考虑线段树。

前两个操作都是单点修改，后一个操作是区间查询。

其中，第二个操作就相当于把 top 点设成 1。

若两数相乘超过 2^{32}，则将其赋为 -1，这样方便分辨。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 5, M = 1ll << 32;

int tree[4 * N], q, top = 0;

int Mul(int x, int y) {
    if (x == 0 || y == 0)
        return 0;
    if (x == -1 || y == -1)
        return -1;
    if (x * y >= M)
        return -1;
    return x * y;
}

void push_up(int u, int l, int r) {
    tree[u] = Mul(tree[2 * u], tree[2 * u + 1]);
    return;
}

void build(int u, int l, int r) {
    if (l == r) {
        tree[u] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(2 * u, l, mid);
    build(2 * u + 1, mid + 1, r);
    push_up(u, l, r);
    return;
}

int query(int u, int l, int r, int X, int Y) {
    if (Y < l || r < X)
        return 1;
    if (X <= l && r <= Y)
        return tree[u];
    int mid = (l + r) >> 1;
    int tmp1 = query(2 * u, l, mid, X, Y);
    int tmp2 = query(2 * u + 1, mid + 1, r, X, Y);
    return Mul(tmp1, tmp2);
}

void update(int u, int l, int r, int X, int val) {
    if (X < l || r < X)
        return;
    if (X == l && r == X) {
        tree[u] = val;
        return;
    }
    int mid = (l + r) >> 1;
    update(2 * u, l, mid, X, val);
    update(2 * u + 1, mid + 1, r, X, val);
    push_up(u, l, r);
    return;
}

signed main() {
    cin >> q;
    build(1, 1, q);
    for (int i = 1; i <= q; i++) {
        int op, x, y;
        cin >> op;
        if (op == 1) {
            cin >> x;
            top++;
            update(1, 1, q, top, x);
        } else if (op == 2) {
            if (top > 0)
                update(1, 1, q, top--, 1);
        } else {
            cin >> y;
            if (y > top) {
                cout << "ERROR\n";
            } else {
                int tmp = query(1, 1, q, top - y + 1, top);
                if (tmp <= -1)
                    cout << "OVERFLOW\n";
                else
                    cout << tmp << "\n";
            }
        }
    }
    return 0;
}