题解：P13677 [GCPC 2023] Loop Invariant

· · 题解

P13677 [GCPC 2023] Loop Invariant

题目概括

有一串由 ( 和 ) 组成的字符串，括号配对。

要求在其中找到一个开头不为原字符串开头，长度与原字符串一样，且括号配对的字符串。

然而如果有多种答案需要输出开头最靠前的那个（虽然没说）。不存在则输出 no。

思路

可以想到，只有当字符串内有多个不全相同的括号匹配的小段，才能通过调换小段的顺序达到目的。

所以，先将读入的字符串 S 分成括号匹配的小段，存入字符串数组 S2。然后遍历 S2 中的字符串，如果全部相同则输出 no，否则继续。

然后从 S2[2] 开始输出（默认从一位开始），最后输出 S2[1] 便是答案了。

如样例中的 ()(())() 就可以分成 ()、(()) 和 ()。我们按照上述规则输出 (())()() 即可。

代码

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

string S;
string S2[1000005];     //这里要开10^6 
int flag=0;
int cnt=1;
bool isno=1;

int main(){
    cin >> S;
    for (int i=0;i<S.length();i++){     //喜闻乐见的字符串操作 
        if (S[i]=='(') flag++;
        else flag--;
        S2[cnt]+=S[i];
        if (flag==0) cnt++;
    }
    cnt--;      //这里最后多了一个，减掉 
    for (int i=1;i<cnt;i++){        //判断是否全部相等 
        if (S2[i]!=S2[i+1]){
            isno=0;
            break;
        }
    }
    if (isno) cout << "no";
    else{       //否则先输出第二位，最后输出第一位 
        for (int i=2;i<=cnt;i++) cout << S2[i];
        cout << S2[1];
    }
    return 0;
}

所有操作都标注在里面了，如果有不会的可以试着自己推导一下。