专栏文章

题解：P13677 [GCPC 2023] Loop Invariant

DDoraeman
P13677题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miodtdvj
此快照首次捕获于
2025/12/02 17:34
3 个月前
此快照最后确认于
2025/12/02 17:34
3 个月前
查看原文

大致题意

给定一个字符串 SS（长度不超过 10610^6），仅由 ( 和 ) 组成，且括号配对。
求一个字符串 S′S'，必须括号配对。S′S' 以 SS 的某个字符 SiS_i 开头，直到 SS 的结尾结束，再从 SS 的开头开始，以 Si−1S_{i-1} 结束。要求 S′≠SS'\not=S。在 S′S' 符合要求时最小化 ii。
即：S′=Si∼(∣S∣−1)+S1∼iS'=S_{i\sim (|S|-1)}+S_{1\sim i}（SS 下标以 00 开头，0≤i<∣S∣0\le i<|S|，++ 表示字符串拼接）。
如果不存在这样的字符串 S′S'，输出 no。
注：以上加粗字体提到，要在 S′S' 符合要求时最小化 ii，因为本题没有开 SPJ（别问我怎么知道的）。

思路

分割字符串

将字符串 SS 分割成若干个小字符串，使每个字符串各自的括号能够配对，并且最小化各个小字符串的长度。
例：字符串 ()(()())(()) 被分割为 ()、(()())、(()) 这 33 个字符串。

分情况讨论

无解情况

显然，一定存在某些字符串 SS，使我们找不到任何一个字符串 S′S' 符合要求。
如果不考虑 S′≠SS'\not=S 的要求，单纯想要按照规定构造出一个括号配对的字符串 S′S' 非常容易（根据刚才分割的字符串组合新的字符串）。
但是可能无法满足 S′≠SS'\not=S 的要求。
观察发现：如果 SS 分割得到的多个字符串都相等，那么一定无法满足 S′≠SS'\not=S 的要求，直接输出 no。

有解情况

反之，如果多个字符串并非都相等，就可以得到正确的 S′S'。
由于需要最小化 ii（S′S' 的开头在 SS 中的下标），所以直接将 S′S' 设为分割后多个小字符串中，从第二个到最后一个，再拼接第一个小字符串。

代码

CPP
#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]);
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...