3-13

[蓝桥杯2017初赛]正则问题

题目描述
考虑一种简单的正则表达式：只由 x ( ) | 组成的正则表达式。
小明想求出这个正则表达式能接受的最长字符串的长度。
例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6

输入
输入一个由x()|组成的正则表达式。输入长度不超过100，保证合法。

输出
输出这个正则表达式能接受的最长字符串的长度。

样例输入
((xx|xxx)x|(x|xx))xx
样例输出
6

参考:https://blog.csdn.net/qq_43328587/article/details/104427256

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e9+5;

string a;
int ans=0;
int i=0;
int dfs(){
	int low=0,le=0;
	for(;i<a.size();){
		if(a[i]=='('){
			i++;
			low=low+dfs();
		}
		else if(a[i]=='x'){
			i++;
			low++;
		}
		else if(a[i]=='|'){
			i++;
			le=max(le,low);
			low=0;
		}
		else {
			i++;
			break;
		}
	}
	return max(low,le);
}

int main(){
	 cin>>a;
	 ans=dfs();
	 cout<<ans<<endl;
}

[蓝桥杯2017初赛]包子凑数

题目描述
小明几乎每天早晨都会在一家包子铺吃早餐。这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子
每种蒸笼都有非常多笼，可以认为是无限笼。
每当有顾客想买X个包子，卖包子的大叔就会选出若干笼包子来，使得这若干笼中恰好一共有X个包子。
比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。
当然有时包子大叔无论如何也凑不出顾客想买的数量。
比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。

输入
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)

输出
输出一行包含一个整数代表答案。如果凑不出的数目有无限多个，输出INF。

样例输入
2
4
5
样例输出
6

参考：https://blog.csdn.net/qq_44577309/article/details/104376648

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e9+5;

int n,a[105],dp[10005];

int main(){
	scanf("%d",&n);
	dp[0]=1;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	int gcd=a[1];
	for(int i=1;i<=n;i++){
		gcd=__gcd(gcd,a[i]);
	}
	if(gcd!=1){
		cout<<"INF"<<endl;
	}
	else{
		for(int i=1;i<=n;i++){
			for(int j=0;j+a[i]<=10000;j++){
				if(dp[j]){
					dp[j+a[i]]=1;	
				}
			}
		}
		int ans=0;
		for(int i=1;i<=10000;i++){
			if(dp[i]==0){
				//cout<<i<<endl;
				ans++;
			}
		}
		cout<<ans<<endl;
	}
}