题解归档 - cf2224C

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

• 本地编号：cf2224C
• 本地来源：problems/cf2224C/idea.md
• 题目链接：https://codeforces.com/contest/2224/problem/C
• 原始标题：cf2224C - Zhily and Bracket Swapping

思路

cf2224C - Zhily and Bracket Swapping

Pattern

At every position there are two cases:

• same column (( or )): both strings receive the same bracket, fixed;
• mixed column () or )(: one string receives ( and the other receives
  ), and we may choose the orientation.

Let depth be the common contribution of same columns:

• (( increases depth;
• )) decreases depth;
• mixed columns do not change depth.

Let x be the difference between the two row balances caused by mixed columns.
Both row balances are nonnegative iff |x| <= depth.

Claim

If depth == 0, a mixed column is impossible, because it would make one row
balance -1.

Between two moments where depth is 0, the depth is always positive. In such
an excursion, mixed columns can be oriented alternately, keeping x equal to
0 or 1, so the only requirement is that the number of mixed columns in that
excursion is even. If it is odd, x cannot return to 0 when depth returns
to 0.

Therefore scan left to right:

• same columns must form a regular bracket sequence by depth;
• mixed columns are forbidden at depth == 0;
• each positive-depth excursion must contain an even number of mixed columns.

Complexity

O(n) per test case.

代码

来源：problems/cf2224C/solution.cpp

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        int n;
        string a,b;
        cin>>n>>a>>b;
        int depth=0,par=0;
        bool ok=true;
        for(int i=0;i<n;i++){
            if(a[i]==b[i]){
                if(a[i]=='(') depth++;
                else{
                    depth--;
                    if(depth<0) ok=false;
                    if(depth==0){
                        if(par) ok=false;
                        par=0;
                    }
                }
            }else{
                if(depth==0) ok=false;
                par^=1;
            }
        }
        if(depth!=0||par) ok=false;
        cout<<(ok?"YES":"NO")<<"\n";
    }
    return 0;
}