专栏文章

数据结构

ssccc_
个人记录参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minivs64
此快照首次捕获于
2025/12/02 03:08
3 个月前
此快照最后确认于
2025/12/02 03:08
3 个月前
查看原文

P14172 【MX-X23-T2】括号串

错因：思路细节错误，有可能虽然相邻两个是 )(，但是可能原本就是匹配的，改了之后反倒不匹配了。
思路：当遇到 ( 时，将他压进栈，否则，若栈内还有未匹配的括号，则 stk.pop()，再否则，判断是否用过一次机会，是的话就无解，否则使用一次机会。
C
#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 提高组] 导弹拦截

第一问：求最长不上升子序列长度。
第二问：求要多少个不上升子序列才能覆盖原数组——即最长上升子序列的长度。
对于 dpdp，O(n2)O(n^2) 的方法只有一半分数，考虑树状数组优化 dpdp。
树状数组存储比 xx 小的最大 dpdp 值。
对于第一问，我们可以把它当成最长后缀不下降子序列。
状态：dpidp_i 表示后面 ii 个数的最长后缀不下降子序列长度。
答案：max⁡(dpi)\max(dp_i)。
状态转移方程：dpi=query(ai)+1dp_i = query(a_i) + 1。
初始化：dpi=1dp_i = 1。
对于第二问，我们可以把它当成最长上升子序列。
状态：dpidp_i 表示前 ii 个数的最长上升子序列长度。
答案：max⁡(dpi)\max(dp_i)。
状态转移方程：dpi=query(ai−1)+1dp_i = query(a_i - 1) + 1，因为是严格上升。
初始化：dpi=1dp_i = 1。
CPP
#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. 考虑每个 aia_i 成为最小值的贡献；
  2. 对于某个最小值 aia_i，若可以在长度为 lenlen 的区间内成为最小值，那么在长度在 [1,len][1,len] 的所有长度的区间都可以成为最小值，从而参与对于长度区间的最大值竞争；
  3. 预处理 aia_i 成为最小值的最长区间，显然用单调栈维护；
  4. 维护 li,ril_i, r_i 表示 aia_i 成为最小值的最小下标和最大下标；
  5. ansri−li+1=max⁡(ansri−li+1,ai)ans_{r_i - l_i + 1} = \max(ans_{r_i - l_i + 1}, a_i)；
  6. 倒序枚举区间长度 lenlen 从 nn 到 11，anslen=max⁡(anslen,anslen+1)ans_{len} = \max(ans_{len}, ans_{len + 1})。
CPP
#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 第二场] 栈与乘积

考虑线段树。
前两个操作都是单点修改，后一个操作是区间查询。
其中，第二个操作就相当于把 toptop 点设成 11。
若两数相乘超过 2322^{32}，则将其赋为 −1-1，这样方便分辨。
CPP
#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;
}

评论

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

正在加载评论...