题解：P12271 [蓝桥杯 2024 国 Python B] 括号与字母

Crasole · 2025-05-07 08:54:58 · 题解

题目的意思可以理解为统计每个字符在每个括号中出现了几次，那么我们就可以用一个栈来进行括号匹配，顺便把字符在括号中出现等次数统计一下，又因为题目中说，字符的个数是不小于 x_i 个，也就是说，对于当前的括号，如果字符 c 的个数是 cnt，那么它对 0 到 cnt 的询问都能产生贡献，所以可以写一个前缀和。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int m;
bool vis[N];
string t;
int f[30][N];
//f是答案数组

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> t;
    m = t.size(), t = " " + t;
    stack < vector <int> > stk;
//括号匹配
    for (int i = 1; i <= m; ++i) {
        if(t[i] == ')') {
            vector <int> a(30);
            while(stk.size()) {
                vector <int> tmp = stk.top();
                stk.pop();
                if(tmp[26]) {
                    if(tmp[26] == '(') break;
                    ++ a[tmp[26] - 'a'];
                }
                else {
                    for (int i = 0; i < 26; ++i) 
                        a[i] += tmp[i];
                }
            }
            //统计贡献
            for (int i = 0; i < 26; ++i)
                ++ f[i][0], -- f[i][a[i] + 1];
            stk.push(a);
        } else {
            vector <int> a(30);
            a[26] = t[i];
            stk.push(a);
        }
    }
    for (int i = 0; i <= 25; ++i)
        for (int j = 1; j <= m; ++j)
            f[i][j] += f[i][j - 1];
    int q;
    cin >> q;
    while(q --) {
        char c;
        int x;
        cin >> c >> x;
        cout << f[c - 'a'][x] << '\n';
    }
    return 0;
}