1 second
256 megabytes
standard input
standard output
You are given string
s consists of opening and closing brackets of four kinds
<>,
{},
[],
(). There are two types of brackets: opening and closing. You can replace any bracket by another of the same type. For example, you can replace< by the
bracket
{, but you can't replace it by
) or
>.
The following definition of a regular bracket sequence is well-known, so you can be familiar with it.
Let's define a regular bracket sequence (RBS). Empty string is RBS. Let
s1 ands2
be a RBS then the strings<s1>s2,{s1}s2,[s1]s2,(s1)s2
are also RBS.
For example the string "[[(){}]<>]" is RBS, but the strings "[)()"
and "][()()" are not.
Determine the least number of replaces to make the string
s RBS.
The only line contains a non empty string
s, consisting of only opening and closing brackets of four kinds. The length ofs does not exceed106.
If it's impossible to get RBS from
s print
Impossible.
Otherwise print the least number of replaces needed to get RBS from
s.
[<}){}
2
{()}[]
0
]]
Impossible
该题意思大概就是要形成正确的括号形式,左括号之间可以相互变换,右括号之间也可以相互变换,但左右括号之间不能相互变换。求出最小变换次数。 可以用STL中的stack解决,但没学过就用数组进行模拟压栈。
#include<stdio.h>
#include<string.h>
int main()
{
char a[1000005],b[1000000];
int n,j=0,sum=0,sum2=0;
scanf("%s",a);
n=strlen(a);
for(int i=0;i<n;i++)
{
b[j]=a[i];
if(sum2<0)
{
printf("Impossible\n");
return 0;
}
switch(a[i])//利用ASCII码进行判断,如果匹配则弹出
{
case '{':j++;sum2++;break;
case '[':j++;sum2++;break;
case '(':j++;sum2++;break;
case '<':j++;sum2++;break;
case '}':if(b[j-1]+2==a[i]){j--;}else{j--;sum++;}sum2--;break;
case ']':if(b[j-1]+2==a[i]){j--;}else{j--;sum++;}sum2--;break;
case ')':if(b[j-1]+1==a[i]){j--;}else{j--;sum++;}sum2--;break;
case '>':if(b[j-1]+2==a[i]){j--;}else{j--;sum++;}sum2--;break;
}
}
if(sum2!=0)
{
printf("Impossible\n");
return 0;
}
printf("%d\n",sum); return 0;
}
CodeForces - 612C Replace To Make Regular Bracket Sequence 压栈的更多相关文章
-
CF 612C. Replace To Make Regular Bracket Sequence【括号匹配】
[链接]:CF [题意]:给你一个只含有括号的字符串,你可以将一种类型的左括号改成另外一种类型,右括号改成另外一种右括号 问你最少修改多少次,才能使得这个字符串匹配,输出次数 [分析]: 本题用到了栈 ...
-
Educational Codeforces Round 4 C. Replace To Make Regular Bracket Sequence 栈
C. Replace To Make Regular Bracket Sequence 题目连接: http://www.codeforces.com/contest/612/problem/C De ...
-
Replace To Make Regular Bracket Sequence
Replace To Make Regular Bracket Sequence You are given string s consists of opening and closing brac ...
-
D - Replace To Make Regular Bracket Sequence
You are given string s consists of opening and closing brackets of four kinds <>, {}, [], (). ...
-
Educational Codeforces Round 4 C. Replace To Make Regular Bracket Sequence
题目链接:http://codeforces.com/contest/612/problem/C 解题思路: 题意就是要求判断这个序列是否为RBS,每个开都要有一个和它对应的关,如:<()> ...
-
Codeforces Beta Round #5 C. Longest Regular Bracket Sequence 栈/dp
C. Longest Regular Bracket Sequence Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://codeforces.c ...
-
(CodeForces - 5C)Longest Regular Bracket Sequence(dp+栈)(最长连续括号模板)
(CodeForces - 5C)Longest Regular Bracket Sequence time limit per test:2 seconds memory limit per tes ...
-
贪心+stack Codeforces Beta Round #5 C. Longest Regular Bracket Sequence
题目传送门 /* 题意:求最长括号匹配的长度和它的个数 贪心+stack:用栈存放最近的左括号的位置,若是有右括号匹配,则记录它们的长度,更新最大值,可以在O (n)解决 详细解释:http://bl ...
-
Almost Regular Bracket Sequence CodeForces - 1095E (线段树,单点更新,区间查询维护括号序列)
Almost Regular Bracket Sequence CodeForces - 1095E You are given a bracket sequence ss consisting of ...
随机推荐
-
yii2 RESTful api的详细使用
作者:白狼 出处:http://www.manks.top/yii2-restful-api.html 本文版权归作者,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则 ...
-
如何将util.Date转化为sql.Date
通过查看API可以很容易知道,util.Date类时sql.Date的父类,所以根据向上转型的原理可以很简单的知道时可行的,不用做转换都可以. 但是如果想要将util.Date转化为sql.Date, ...
-
设计模式之Builder模式
一.感性认识 二.Builder模式 1.定义 一个复杂对象的构建与其表示相分离,使得同样的构建过程可以创建不同的表示.即构建过程相同,但是子部件却不相同. 2.结构说明 Builder: 创建者接口 ...
-
[AFN]AFNetworking错误总结
1. 错误打印 code=-1016 filed: text/html 错误原因:AFN默认不能解析请求回来的text/html数据 解决办法: AFN3.0的请看这里 AFHTTPSessionM ...
-
【博弈论】HDU 5754 Life Winner Bo
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5754 题目大意: 4种棋子,象棋中的 1王,2车,3马,4后,选其一,B和G轮流走,不能往左上走,一 ...
-
SharePoint 2013 设置自己定义布局页
在SharePoint中.我们常常须要自己定义登陆页面.错误页面.拒绝訪问等:不知道大家怎样操作,曾经自己常常在原来页面改或者跳转.事实上SharePoint为我们提供了PowerShell命令,来改 ...
-
js 根据身份证号获取性别,年龄,等
$(function(){ $("#corpOwnerIdno").blur(function(){ //获取输入身份证号码 ...
-
python 将本地目录暴露为http服务
python3 nohup python3 -m http.server 8080 &
-
python range用法
1. range(n) 相当于枚举 从0<=i<n的整数 增量为1 for i in range(4): print(i) 结果:0 1 2 3 2. range(5,10) 相当于枚举 ...
-
R kernel for Jupyter Notebook 支持r
1/2) Installing via supplied binary packages(default on Windows + Mac OS X) You can install all pack ...