CodeForces - 612C Replace To Make Regular Bracket Sequence 压栈

时间:2022-10-11 12:21:55
C. Replace To Make Regular Bracket Sequence
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

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.

Input

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.

Output

If it's impossible to get RBS from
s print
Impossible.

Otherwise print the least number of replaces needed to get RBS from
s.

Examples
Input
[<}){}
Output
2
Input
{()}[]
Output
0
Input
]]
Output
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 压栈的更多相关文章

  1. CF 612C&period; Replace To Make Regular Bracket Sequence【括号匹配】

    [链接]:CF [题意]:给你一个只含有括号的字符串,你可以将一种类型的左括号改成另外一种类型,右括号改成另外一种右括号 问你最少修改多少次,才能使得这个字符串匹配,输出次数 [分析]: 本题用到了栈 ...

  2. Educational Codeforces Round 4 C&period; Replace To Make Regular Bracket Sequence 栈

    C. Replace To Make Regular Bracket Sequence 题目连接: http://www.codeforces.com/contest/612/problem/C De ...

  3. Replace To Make Regular Bracket Sequence

    Replace To Make Regular Bracket Sequence You are given string s consists of opening and closing brac ...

  4. D - Replace To Make Regular Bracket Sequence

    You are given string s consists of opening and closing brackets of four kinds <>, {}, [], (). ...

  5. Educational Codeforces Round 4 C&period; Replace To Make Regular Bracket Sequence

    题目链接:http://codeforces.com/contest/612/problem/C 解题思路: 题意就是要求判断这个序列是否为RBS,每个开都要有一个和它对应的关,如:<()&gt ...

  6. Codeforces Beta Round &num;5 C&period; Longest Regular Bracket Sequence 栈&sol;dp

    C. Longest Regular Bracket Sequence Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://codeforces.c ...

  7. (CodeForces - 5C)Longest Regular Bracket Sequence(dp&plus;栈)(最长连续括号模板)

    (CodeForces - 5C)Longest Regular Bracket Sequence time limit per test:2 seconds memory limit per tes ...

  8. 贪心&plus;stack Codeforces Beta Round &num;5 C&period; Longest Regular Bracket Sequence

    题目传送门 /* 题意:求最长括号匹配的长度和它的个数 贪心+stack:用栈存放最近的左括号的位置,若是有右括号匹配,则记录它们的长度,更新最大值,可以在O (n)解决 详细解释:http://bl ...

  9. Almost Regular Bracket Sequence CodeForces - 1095E (线段树,单点更新,区间查询维护括号序列)

    Almost Regular Bracket Sequence CodeForces - 1095E You are given a bracket sequence ss consisting of ...

随机推荐

  1. yii2 RESTful api的详细使用

    作者:白狼 出处:http://www.manks.top/yii2-restful-api.html 本文版权归作者,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则 ...

  2. 如何将util&period;Date转化为sql&period;Date

    通过查看API可以很容易知道,util.Date类时sql.Date的父类,所以根据向上转型的原理可以很简单的知道时可行的,不用做转换都可以. 但是如果想要将util.Date转化为sql.Date, ...

  3. 设计模式之Builder模式

    一.感性认识 二.Builder模式 1.定义 一个复杂对象的构建与其表示相分离,使得同样的构建过程可以创建不同的表示.即构建过程相同,但是子部件却不相同. 2.结构说明 Builder: 创建者接口 ...

  4. &lbrack;AFN&rsqb;AFNetworking错误总结

    1. 错误打印  code=-1016 filed: text/html 错误原因:AFN默认不能解析请求回来的text/html数据 解决办法: AFN3.0的请看这里 AFHTTPSessionM ...

  5. 【博弈论】HDU 5754 Life Winner Bo

    题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5754 题目大意: 4种棋子,象棋中的 1王,2车,3马,4后,选其一,B和G轮流走,不能往左上走,一 ...

  6. SharePoint 2013 设置自己定义布局页

    在SharePoint中.我们常常须要自己定义登陆页面.错误页面.拒绝訪问等:不知道大家怎样操作,曾经自己常常在原来页面改或者跳转.事实上SharePoint为我们提供了PowerShell命令,来改 ...

  7. js 根据身份证号获取性别,年龄,等

    $(function(){        $("#corpOwnerIdno").blur(function(){          //获取输入身份证号码             ...

  8. python 将本地目录暴露为http服务

    python3 nohup python3 -m http.server 8080 &

  9. python range用法

    1. range(n) 相当于枚举 从0<=i<n的整数 增量为1 for i in range(4): print(i) 结果:0 1 2 3 2. range(5,10) 相当于枚举 ...

  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 ...