CF1101B Accordion 题解

PART 01:思路

我们知道最后的字符串一定是一个左右两边为括号的串,所以先找一波括号。

  • 第一步,找左右括号。

接着在两个括号之间找出两个冒号,所以还要存下左右括号的下标

  • 第一步,找左右括号并存下下标。
  • 第二步,找左右冒号。

最后在两个冒号之间找 \(|\) 字符,所以还要存下冒号的下标

  • 第一步,找左右括号并存下下标。
  • 第二步,在左右括号之间找左右冒号并存下下标(这里可以搞一搞资源重复利用)。
  • 第三步,找左右冒号之间的 \(|\) 符号,并记录有多少个 \(|\) ,最终答案则是4加上 \(|\) 的个数。

PART 02:算法

2.1:初始化+找左右括号

int length=0;
string a;
cin>>a;
length=a.length();
int left=-1;
int right=-1;
for(int i=0;i<length;i++){
	if(a[i]=='['&&left==-1){
		left=i;
	}
	if(a[i]==']'){
		right=i;
	}
}

要点1:之所以要使用 length 变量来表示字符串 a 的长度,是为了之后使用方便,不必反复用函数读取,好习惯。

要点2由于字符串下标从0开始,变量必须先赋值为负数,-1 较为方便。

要点3A为了避免存在多个左括号,一定要保留最先出现的左括号下标!

要点3B:右括号为了找出最后出现的一个,遇到一个变一个,因为 i 在逐渐增大。

2.2:第一处合法性判断

if(left==-1||right==-1){
	cout<<"-1"<<endl;
	return 0;
}

显然,如果 left 没有变化(即没有左括号)或者 right 没有变化(即没有右括号),这个串是非法的。

2.3:初始化+找左右冒号

int l=-1;
int r=-1;
int flag=0;
for(int i=left+1;i<right;i++){
	if(a[i]==':'&&flag==1){
		r=i;
	}
	if(a[i]==':'&&flag==0){
		flag=1;
		l=i;
}

要点1flag 的作用在于确认是否是第一个冒号,如果是,执行第二个 if 中的内容(确定左下标并改变 flag);否则执行第一个 if 中的内容(确定右下标)。

要点2利用 flag 我们也实现了找出最小下标的左冒号与最大下标的右冒号,使得串最长化

要点3:观察循环初始化与条件,发现我们是在左右括号内进行搜找(所以要记下两个括号的下标)

要点4第二个 if 必须放在第一个 if 的后面,否则遇到第一个冒号时,改变了 flag 的值,导致另外一个 if 不恰当开始。

2.4:第二处合法性判断

if(l==-1||r==-1){
	cout<<"-1"<<endl;
	return 0;
} 

显然的,当找不出左冒号(变量 l 无变化)或右冒号(变量 r 无变化)时,该串不合法

2.5:找 \(|\) 符号

int cnt=0;
for(int i=l+1;i<r;i++){
	if(a[i]=='|'){
		cnt++;
	}
}

用 cnt 记录两个冒号之中 \(|\) 符号的个数,循环区间为两个冒号之间。

程序最后,直接输出 cnt+4 即可。

PART 03:AC 代码

本题中各部分已经讲得很透彻,不给出完整代码。

AC记录

上一篇:PHP if...else...elseif 语句


下一篇:2021-09-20