打卡信奥刷题（3676）用C++实现信奥题 P12271 [蓝桥杯 2024 国 Python B] 括号与字母

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

题目描述

给定一个仅包含小写字母和括号的字符串 $S$，保证括号可以两两匹配。

给出 $Q$ 组询问，每组询问给出一个小写字母 $c_i$ 和一个数 $x_i$，询问 $S$ 中有多少对匹配的括号之间有不少于 $x_i$ 个 $c_i$。

输入格式

输入的第一行包含一个字符串 $S$。

第二行包含一个整数 $Q$。

接下来 $Q$ 行，每行包含一个小写字母 $c_i$ 和一个整数 $x_i$ 表示一组询问，用一个空格分隔。

输出格式

输出 $Q$ 行，每行包含一个整数，依次表示每个询问的答案。

输入输出样例 #1

输入 #1

((a)()((b)((c))))
3
a 2
b 1
c 1

输出 #1

0
3
4

说明/提示

评测用例规模与约定

• 对于 $40\%$ 的评测用例，$|S|,Q\le 5000$；
• 对于 $70\%$ 的评测用例，$|S|\le 100000$；
• 对于所有评测用例，$1\le |S|\le 10^6$，$1\le Q\le 100000$，$0\le x_i<10^6$。其中 $|S|$ 表示 $S$ 的长度。

C++实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const int M=26;
int n,Q,S[M][N],F[M][N];
string C;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>C>>Q;
n=C.size(),C=" "+C;
stack<int>St;
for(int i=1;i<=n;i++)
{
for(int j=0;j<M;j++)
S[j][i]=S[j][i–1]+(C[i]==j+'a');
if(C[i]=='(')
St.push(i);
if(C[i]==')')
{
int L=St.top();St.pop();
for(int j=0;j<M;j++)
F[j][S[j][i]–S[j][L–1]]++;
}
}
for(int j=0;j<M;j++)
for(int i=n;i>=0;i—)
F[j][i]+=F[j][i+1];
while(Q—)
{
char c;int x;
cin>>c>>x;
cout<<F[c–'a'][x]<<endl;
}
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容