题解归档 - cf2233C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2233C
• 本地来源：problems/cf2233C/idea.md
• 题目链接：https://codeforces.com/contest/2233/problem/C
• 原始标题：cf2233C - Cost of a Bracket Sequence

思路

cf2233C - Cost of a Bracket Sequence

pattern:
bracket matching monoid / iterative deletion

cost:
The longest regular bracket subsequence has length 2 * pairs, where pairs
is the number of matches made by the usual greedy scan.

summary:
For any substring keep:

• pairs: greedy matched pairs inside it.
• open: unmatched opening brackets after matching inside it.
• close: unmatched closing brackets after matching inside it.

Merging summaries A+B adds min(A.open, B.close) cross-boundary pairs.

algorithm:
While we still may delete and the current pairs > 0, build prefix and suffix
summaries over the current undeleted characters. Test every undeleted position
i by merging prefix[i-1] + suffix[i+1]. If the pair count drops by one,
delete i. Repeat.

why optimal:
Deleting one character can reduce the maximum number of matched pairs by at
most one: take any maximum matching before deletion and discard only the pair
touching the deleted character. The loop finds one deletion that reduces the
count by one whenever the current count is positive, so after d deletions the
cost is minimized at 2 * max(0, initial_pairs-d).

check:
For small n, enumerate all deletion masks with at most k removed
characters and compare the achieved cost with this solution.

代码

来源：problems/cf2233C/solution.cpp

#include<bits/stdc++.h>
using namespace std;
struct node{
    int pairs,open,close;
};
node mergeNode(node a,node b){
    int m=min(a.open,b.close);
    return {a.pairs+b.pairs+m,a.open+b.open-m,a.close+b.close-m};
}
node one(char c){
    if(c=='(') return {0,1,0};
    return {0,0,1};
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        int n,k;
        string s;
        cin>>n>>k>>s;
        s=" "+s;
        vector<int> del(n+1,0);
        vector<node> pref(n+1),suf(n+2);
        int used=0;
        while(used<k){
            pref[0]={0,0,0};
            for(int i=1;i<=n;i++){
                pref[i]=pref[i-1];
                if(!del[i]) pref[i]=mergeNode(pref[i],one(s[i]));
            }
            int cur=pref[n].pairs;
            if(cur==0) break;
            suf[n+1]={0,0,0};
            for(int i=n;i>=1;i--){
                suf[i]=suf[i+1];
                if(!del[i]) suf[i]=mergeNode(one(s[i]),suf[i]);
            }
            int pos=-1;
            for(int i=1;i<=n;i++){
                if(del[i]) continue;
                node now=mergeNode(pref[i-1],suf[i+1]);
                if(now.pairs==cur-1){
                    pos=i;
                    break;
                }
            }
            if(pos==-1) break;
            del[pos]=1;
            used++;
        }
        for(int i=1;i<=n;i++) cout<<del[i];
        cout<<"\n";
    }
    return 0;
}