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

guoshengyu1231 · 2025-04-21 20:35:19 · 题解

题意分析

这个问题需要处理字符串中的括号匹配关系，并在匹配的括号对之间统计特定字符的出现次数。但是这题的数据范围很大，显然不能暴力枚举。

具体思路

看来一眼题目后感觉毫无头绪，毕竟这是一道绿题，肯定是有点难度的。但越是难的题目，我们越要大胆的想。因为这并不是一道一眼就看出要用什么算法的题目。你可以去看他的算法标签，基本都是普及组的算法。那他为什么是一道绿题，因为他需要你通过某些转换才能做。也就是说，他本质的算法并不难，其中的转换也很容易理解，只是一起考就变得很难了。那具体怎么转换呢？只能想呗。

回归正题，既然只需要通过某些转换这题就会非常简单，那我们就需要大胆得想该怎么转换。当然，除了要大胆得想，还得要有目的得想。既然这题这么难，那我们就逐个击破。

• 括号匹配处理：

  • 既然题目要求我们在匹配的括号对之间统计特定字符的出现次数，那我们肯定是先预处理所有匹配得括号对，不然怎么降低时间复杂度。
  • 既然要预处理所有匹配的括号对，那怎么预处理所有匹配的括号对呢？这个其实并不难，用栈处理即可。

• 字符统计预处理‌：

  • 既然是在匹配的括号对之间统计字符出现数，都提到之间了，那肯定得更区间有关了。那你想想，既要满足快速查询区间，又是离线处理的数据结构。没错，就是前缀和呀！
  • 现在我们需要思考，这个前缀和数组究竟可以用来表示什么？这个其实很简单，不难想到，既然是统计字符，那肯定是给字符创建前缀和数组。所以我们不妨用 sum_{c,i} 表示表示字符 c 在字符串前 i 个位置中出现的次数。

• 查询处理： 有了前面的铺垫，这里就比较简单了。

  • 对于查询的 c 和 x，遍历所有匹配的括号对 (l, r)。
  • 使用前缀和数组计算区间 [l+1, r-1] 内字符c的数量（因为左右两边的括号不算）： cnt=sum_{c,r-1}-sum_{c,l+1}。
  • 统计 cnt\ge x 的数量。

    代码

#include<bits/stdc++.h>
using namespace std;
string s;
int n;
int sum[26][1000005];//前缀和
int main() {
    cin>>s>>n;
    vector<pair<char, int>> q;//查询
    for(int i=1;i<=n;i++) 
     {
        char c;int x;
        cin>>c>>x;
        q.emplace_back(c, x);//不能用push_back！
     }
    stack<int> st;
    vector<pair<int, int>> p;//统计括号对
    for (int i=0;i<s.size();i++) 
     {
        if (s[i] == '(') st.push(i);
        if (s[i] == ')') 
         {
            int l=st.top();
            st.pop();
            p.emplace_back(l,i);//不能用push_back！
         }
     }
    for (char c='a';c<='z';c++) 
        for (int i=0;i<s.size();i++) 
         sum[c-'a'][i + 1]=sum[c-'a'][i]+(s[i]==c?1:0);//预处理前缀和
    for (auto& i:q) 
       {
        char c=i.first;
        int x=i.second;
        int cnt=0;
        for (auto& j:p) {
            int l=j.first;
            int r=j.second;
            int total = sum[c-'a'][r]-sum[c-'a'][l + 1];
            if (total >= x) cnt++;
        }
        cout<<cnt<<"\n";
     }
    return 0;
}

时间复杂度分析

• 预处理阶段：
  • 括号匹配：O(|S|)。
  • 预处理前缀和：O(|S|)。
• 查询阶段：
  • 每个查询需要检查所有匹配的括号对，最坏情况下 O(m)。（ m 为匹配括号对数）
  • 总时间复杂度：O(Qm)。

    优化

    刚才那个代码只能得 70 分，其余全部 TLE。所以我们现在需要考虑优化时间复杂度。观察数据范围，我们可以预测能通过本题得代码时间复杂度大概在 O(Q \log m) 左右。那我们该想想如何优化时间复杂度。考虑到是要统计 cnt\ge x 的数量，不难想到二分查找。那既然方向有了，接下来我们要想该如何实现。

    \\

我们可以统计关于某个字符，所有括号对包含该字符得个数，到时候直接二分查找个数 \ge x 的括号对数量。

具体的，在统计完前缀和后。枚举每个括号对，再枚举所有字符。让每个字符统计在这个括号对里出现了几次，并记录。

对于每个字符记录得次数进行排序，以便接下来的二分查找。

在每次查询时，对于查询的字符 c，只需要二分查找字符 c 中 \ge x 的个数就行啦！（具体详见代码）

总时间复杂度：O(Q \log m)。

代码

#include<bits/stdc++.h>
using namespace std;
string s;
int n,sum[26][1000005];
int main()
{
    cin>>s>>n;
    vector<pair<char,int> > q(n);
    for(int i=0;i<n;i++) cin>>q[i].first>>q[i].second;
    stack<int> st;
    vector<pair<int,int> > p;
    for(int i=0;i<s.size();i++)
     {
        if(s[i]=='(') st.push(i);
        if(s[i]==')')
         {
            int l=st.top();st.pop();
            p.emplace_back(l,i);
         }   
     }
    for(char c='a';c<='z';c++)
     for(int i=0;i<s.size();i++)
      sum[c-'a'][i+1]=sum[c-'a'][i]+(s[i]==c?1:0);
    unordered_map<char, vector<int> > Counts;
    for(auto& [l,r]:p)
     for(char c='a';c<='z';c++)
      {
        int cnt=sum[c-'a'][r]-sum[c-'a'][l+1];//前缀和计算
        Counts[c].push_back(cnt);//统计每个字符c
      }
    for(auto& [c,v]:Counts) sort(v.begin(),v.end());//排序
    for(int i=0;i<n;i++)
     {
        char ch=q[i].first;
        int x=q[i].second;
        auto& v=Counts[ch];
        int ans=v.end()-lower_bound(v.begin(),v.end(),x);
        cout<<ans<<"\n";
     }
    return 0;
}