upc组队赛7 Star in Parentheses
Star in Parentheses
题目描述
You are given a string S, which is balanced parentheses with a star symbol '*' inserted.
Any balanced parentheses can be constructed using the following rules:
An empty string is balanced.
Concatenation of two balanced parentheses is balanced.
If T is balanced parentheses, concatenation of '(', T, and ')' in this order is balanced.
For example, '()()' and '(()())' are balanced parentheses. ')(' and ')()(()' are not balanced parentheses.
Your task is to count how many matching pairs of parentheses surround the star.
Let Si be the i-th character of a string S. The pair of Sl and Sr (l<r) is called a matching pair of parentheses if Sl is '(', Sr is ')' and the surrounded string by them is balanced when ignoring a star symbol.
输入
The input consists of a single test case formatted as follows.
S
S is balanced parentheses with exactly one '*' inserted somewhere. The length of S is between 1 and 100, inclusive.
输出
Print the answer in one line.
样例输入
((*)())
样例输出
2
题意+题解
题意:有多少个有效的括号对能把星号包起来,如果能和近的消掉的括号不是有效的
如果星号左边出现( , l ++ ,
星号左边出现 ) ,如果 l !=0,l--;
如果星号右边出现( , pl ++ ,
星号右边出现 ) ,如果 pl !=0,l--; 否则r++
那么l 和 r之间的最小值就是括号对的个数
代码
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define rep(i,a,n) for(int i=a;i<n;++i)
#define readc(x) scanf("%c",&x)
#define read(x) scanf("%d",&x)
#define sca(x) scanf("%d",&x)
#define sca2(x,y) scanf("%d%d",&x,&y)
#define sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define print(x) printf("%d\n",x)
#define mst(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x&-x
#define lson(x) x<<1
#define rson(x) x<<1|1
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> P;
const int INF =0x3f3f3f3f;
const int inf =0x3f3f3f3f;
const int mod = 1e9+7;
const int MAXN = 105;
const int maxn =1000010;
using namespace std;
char s[15000];
int main(){
scanf("%s",s);
int flag = 0 ;
int r = 0;
int l = 0;
int pl = 0;
for(int i = 0; i < strlen(s);i++){
if(s[i] == '*') {
flag = 1;
}
if(!flag && s[i] =='(')
l++;
else if(!flag && s[i] ==')'){
if(l) l--;
}
else if(flag && s[i] == '('){
pl++;
}
else if(flag && s[i] == ')'){
if(pl) pl --;
else r++;
}
}
printf("%d\n",l < r ? l : r);
}
最新文章
- 【翻译】设计模式学习系列1---【Design Patterns Simplified: Part 1【设计模式简述:第一部分】】
- django queryset values&;values_list
- WPF oxyPlot 使用总结
- file_get_contents高級用法
- Android中三种onClick事件的实现与对比
- 手机抓包软件Charles安装使用实例 (流媒体播放测试可去下载的时刻检测)
- hashMap底层put和get方法逻辑
- [Unity2D]Tags和Layers
- This absolute uri http://java.sun.com/jsp/jstl/core cannot be resolved in either web.xml or the jar files deployed with this application
- 【转】 JAR、WAR、EAR的使用和区别
- Neutron分析(3)—— neutron-l3-agent
- Oracle 基础 导入数据库 删除用户、删除表空间、删除表空间下所有表
- Java 8 简明教程
- .net 实例化对象
- Selenium webdriver 元素操作
- javascript 手机号码正则表达式验证函数
- jQuery (01) 浏览器的事件模型
- mysql 开发基础系列10 存储引擎 InnoDB 介绍
- 洛谷 P2158 [SDOI2008]仪仗队 解题报告
- Android使用内容提供者实现增删改查操作