题解：B4459 [合肥市小学组 2025 T3] 括号匹配

Dustlpes_CZY · 2026-01-21 22:58:14 · 题解

前言

本篇题解中的字符串均以下标 1 开头，所提到以及代码中的 r 均指加入字符后的字符串长度。

题目大意

给你一个字符串长度 n，匹配数 k，一个长为 n 的字符串。

若字符串中出现 k 个 ( 并紧接着 k 个 ) 时，我们称该子串为匹配串且匹配成功，接着删除它们并将剩余部分拼接起来。求最终的字符串。

思路

一眼模拟话说我现在看到的标签只有栈啊，再一想就是栈实现。

相当于每次输入：若末尾的 s_{r-2k+1} \sim s_r 子串满足匹配条件，就删除这长度为 2k 的子串。

可怎么知道是否满足匹配条件呢？只需知道以 s_i 为结尾的连续 ( 或 ) 的子串长度即可：

• 每次加入字符时计算与前一个字符是否相同，相同则继承前一个字符所在的子串长度并加 1。
• 否则重新开始计算一个新的子串并存入长度为 1，因为该字符本身也算一位。

当末尾的 ) 数量 \ge k 并且字符串长度 \ge 2k 时，我们找到以 s_{r-k} 为结尾的连续 ( 的子串长度进行匹配（不用管 s_{r-2k+1}，因为它是头，我们需要尾就行）：

• 如果以 s_i 为结尾的连续 ( 的子串长度 \ge k：恭喜你，匹配成功！删除这个匹配串。
• 如果以 s_i 为结尾的连续 ( 的子串长度 < k：抱歉，不满足匹配条件，继续等待吧。

AC CODE

本题解代码用数组模拟栈，每次存入以 s_i 为结尾的连续 ( 或 ) 的子串长度 cnt 和字符 ch。

#include <bits/stdc++.h>
#define LL long long
#define the return
#define AK_IOI std
using namespace AK_IOI;
const LL N=1e5+6;
LL T,n,m,ans,ls,r,k;
struct CCTV{
    LL cnt;//子串长度
    char ch;//字符 '(' or ')'
} a[N];
string s;
int main(){ cin.tie(0)->sync_with_stdio(0);cout.tie(0);
    cin>>ls>>k>>s;  s=" "+s;
    for(LL i=1; i<=ls; i++){
        if(r && a[r].ch==s[i]) a[++r]={a[r-1].cnt+1,s[i]};
    //   有字符在栈 并且 可以继承前一个字符 
        else a[++r]={1ll,s[i]};//新加入字符
        while(r>=2*k && a[r].ch==')' && a[r-k].ch=='(' && a[r].cnt>=k && a[r-k].cnt>=k)
            r-=2*k;
        //有就删除
    }
    for(LL i=1; i<=r; i++) cout<<a[i].ch;
    return 0;
}

最后

题解来之不易，审核题解不易，点个赞再走吧！！！

管理员大大辛苦了！！！