P13677 [GCPC 2023] Loop Invariant

题目概括

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

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

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

思路

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

所以，先将读入的字符串

S

分成括号匹配的小段，存入字符串数组

S2

。然后遍历

S2

中的字符串，如果全部相同则输出 no，否则继续。

然后从

S2[2]

开始输出（默认从一位开始），最后输出

S2[1]

便是答案了。

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

代码

CPP

#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;
}

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

题解：P13677 [GCPC 2023] Loop Invariant

文章操作

P13677 [GCPC 2023] Loop Invariant

题目概括

思路

代码

相关推荐

评论

题解：P13677 [GCPC 2023] Loop Invariant