题解：P13677 [GCPC 2023] Loop Invariant

· · 题解

大致题意

给定一个字符串 S（长度不超过 10^6），仅由 ( 和 ) 组成，且括号配对。
求一个字符串 S'，必须括号配对。S' 以 S 的某个字符 S_i 开头，直到 S 的结尾结束，再从 S 的开头开始，以 S_{i-1} 结束。要求 S'\not=S。在 S' 符合要求时最小化 i。
即：S'=S_{i\sim (|S|-1)}+S_{1\sim i}（S 下标以 0 开头，0\le i<|S|，+ 表示字符串拼接）。
如果不存在这样的字符串 S'，输出 no。

注：以上加粗字体提到，要在 S' 符合要求时最小化 i，因为本题没有开 SPJ（别问我怎么知道的）。

思路

分割字符串

将字符串 S 分割成若干个小字符串，使每个字符串各自的括号能够配对，并且最小化各个小字符串的长度。

例：字符串 ()(()())(()) 被分割为 ()、(()())、(()) 这 3 个字符串。

分情况讨论

无解情况

显然，一定存在某些字符串 S，使我们找不到任何一个字符串 S' 符合要求。

如果不考虑 S'\not=S 的要求，单纯想要按照规定构造出一个括号配对的字符串 S' 非常容易（根据刚才分割的字符串组合新的字符串）。
但是可能无法满足 S'\not=S 的要求。

观察发现：如果 S 分割得到的多个字符串都相等，那么一定无法满足 S'\not=S 的要求，直接输出 no。

有解情况

反之，如果多个字符串并非都相等，就可以得到正确的 S'。

由于需要最小化 i（S' 的开头在 S 中的下标），所以直接将 S' 设为分割后多个小字符串中，从第二个到最后一个，再拼接第一个小字符串。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;

int a[N], cnt, L, R;
string s;

int main(){
    cin >> s;
    for(int i=0; i<s.size(); i++){
        if(L == R) // 此时可以分割了! 
            a[++cnt] = i, // 分割字符串端点 
            L = R = 0;
        if(!i && cnt) --cnt; // 如果a[cnt]=0, 删除无用信息 

        // 左右括号匹配 
        L += (s[i] == '('),
        R += (s[i] == ')');
    }
    // 最后一个也可以进行匹配 
    a[++cnt] = s.size();

    bool flag = 0;
    string head = s.substr(0, a[1]); // 分割后第一个小字符串 
    for(int i=2; i<=cnt; i++){
        int x = a[i-1], y = a[i];
        // s2 = s[x,y)
        string s2 = s.substr(x, y-x); // 分割后其余小字符串 
        if(s2 != head){ // 并非全部相等 
            flag = 1;
            break;
        }
    }

    if(!flag){ // 全部相等, 无解 
        cout << "no";
        return 0;
    } 

    // 有解, 最小化i, 由于i=0时S'=S, 所以i=1
    cout << s.substr(a[1]);
    cout << s.substr(0, a[1]);
}