自动搬运

查看原文

来自洛谷，原作者为

	Patpowder ?Pat?pow?der?

搬运于2025-08-24 22:41:04，当前版本为作者最后更新于2023-07-10 10:55:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8650 [蓝桥杯 2017 省 A] 正则问题

既然标签是递归，那就来一个递归的题解吧！

tips:本题解与其他题解代码相似，主要是思维解释。

AC Code:

省的你们翻得累死。

#include <bits/stdc++.h>
using namespace std;
int re(int ans){
	char c;
	while(cin>>c){
		if(c == '\r' || c == '\n') return ans;
		else if(c == 'x') ans ++;
	   else if(c == '(') ans += re(0);
		else if(c == ')') return ans;
		else if(c == '|') return max(ans, re(0));
	}
	return ans;
} 
int main() {
	cout<<re(0);
	return 0;
}
//很短，对吧

解释

首先要有对递归的思路：

定义操作：re(int ans) 函数；

必要参数：int ans 用来记录当前的答案；

子操作：

循环输入字符，每输入一个字符就判断这个字符是什么?

1. 是 x 则将 $ans$ 增加；

2. 是 ( 则进入递归，统计括号内的字符数，也就是 $re(0)$，同时将答案增加返回值；

3. 是 ) 则将当前答案返回；

4. 是 | 则计算当前的答案和接下来的答案的最大值，也就是 $ans + f(0)$。

边界：输入完了，退出。

补充一下 | 的芝士：

返回 | 左边和右边的答案的最大值，比如 xxxx|xxxxxxxxx 就会返回 $9$。