cf-Round551-Div2-C. Serval and Parenthesis Sequence(贪心)

时间:2022-08-29 18:09:33

题目链接:http://codeforces.com/contest/1153/problem/C

题意:给定由'(',')','?'组成的字符串,问是否能将其中的?全部换成'(‘,’)'使得字符串的任意非空真字串不构成正确的括号表达式,而整个字符串构成括号表达式,其中正确的括号表达式是指通过插入'1','+'能构成算术式。

思路:我们记'('为-1,')'为1,显然所有字串应满足前面的和<0,字串等于0的话就不满足字串不构成正确的括号表达式了,且整个字符串的和=0(题目可能出现'((((??'这样的数据,即无法构成正确的括号表达式的。我们用n1表示需要添加的'('的数量,n2表示要添加的')'的数量,利用贪心思想,将前n1个?全部换成'(',将剩下的?全换成')’。然后从头检查一遍即可。

AC代码:

#include<bits/stdc++.h>
using namespace std; int n,n1,n2,flag=;
char s[]; int main(){
scanf("%d",&n);
if(n%==){
printf(":(\n");
return ;
}
scanf("%s",s);
for(int i=;i<n;++i)
if(s[i]=='(') ++n1;
else if(s[i]==')') ++n2;
n1=n/-n1,n2=n/-n2;
int k=;
for(int i=;i<n1;)
if(s[k++]=='?') s[k-]='(',++i;
for(int i=;i<n2;)
if(s[k++]=='?') s[k-]=')',++i;
int tmp=;
for(int i=;i<n-;++i){
if(s[i]=='(') --tmp;
else ++tmp;
if(tmp>=){
flag=;
break;
}
}
if(s[n-]=='(') --tmp;
else ++tmp;
if(tmp!=) flag=;
if(flag)
printf("%s\n",s);
else
printf(":(\n");
return ;
}

cf-Round551-Div2-C. Serval and Parenthesis Sequence(贪心)的更多相关文章

  1. CF1153C Serval and Parenthesis Sequence

    题目地址:CF1153C Serval and Parenthesis Sequence 思路:贪心 如果有解,那么 \(s_0 = (\) && \(s_{n-1} = )\) &a ...

  2. C&period; Serval and Parenthesis Sequence 【括号匹配】 Codeforces Round &num;551 &lpar;Div&period; 2&rpar;

    冲鸭,去刷题:http://codeforces.com/contest/1153/problem/C C. Serval and Parenthesis Sequence time limit pe ...

  3. Serval and Parenthesis Sequence【思维】

    Serval and Parenthesis Sequence 题目链接(点击) Serval soon said goodbye to Japari kindergarten, and began ...

  4. cf——C&period; Serval and Parenthesis Sequence

    括号正确匹配问题,应该不难 #include <iostream> #include <cstring> #include <string> #include &l ...

  5. Serval and Parenthesis Sequence CodeForces - 1153C

    题目大意:一个字符串只含有? ( ),?可以变成 ) 或者 ( ,将字符串中所有的?变成) 或者 ( 使得字符串合法. 合法就是让括号配对,并且不可以提前结束比如:()()这样是不合法的. 题解:既然 ...

  6. cf 442 div2 F&period; Ann and Books&lpar;莫队算法&rpar;

    cf 442 div2 F. Ann and Books(莫队算法) 题意: \(给出n和k,和a_i,sum_i表示前i个数的和,有q个查询[l,r]\) 每次查询区间\([l,r]内有多少对(i, ...

  7. HDU5014Number Sequence&lpar;贪心&rpar;

    HDU5014Number Sequence(贪心) 题目链接 题目大意: 给出n,然后给出一个数字串,长度为n + 1, 范围在[0, n - 1].然后要求你找出另外一个序列B,满足上述的要求,而 ...

  8. 【题解】Cut the Sequence&lpar;贪心区间覆盖&rpar;

    [题解]Cut the Sequence(贪心区间覆盖) POJ - 3017 题意: 给定一大堆线段,问用这些线段覆盖一个连续区间1-x的最小使用线段的数量. 题解 考虑一个这样的贪心: 先按照左端 ...

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

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

随机推荐

  1. C&plus;&plus;中&OpenCurlyDoubleQuote;强制转换”的四大天王

    哈哈,这个标题有点搞笑了!笑一笑,十年少,希望大家都嗨心! 在C++中主要有四种强制类型转换:static_cast,reinterpret_cast,const_cast,dynamic_cast. ...

  2. 门户级UGC系统的技术进化路线——新浪新闻评论系统的架构演进和经验总结(转)

    add by zhj:先收藏了 摘要:评论系统是所有门户网站的核心标准服务组件之一.本文作者曾负责新浪网评论系统多年,这套系统不仅服务于门户新闻业务,还包括调查.投票等产品,经历了从单机到多机再到集群 ...

  3. spring中配置jndi数据源

    spring  AplicationContext.xml中的配置 <bean id="dataSource1" class="org.springframewor ...

  4. &lbrack;Yii2&rsqb;Unable to verify your data submission&lpar;你提交的资料无法被验证&rpar;

    Yii2中,使用form提交数据,会提示: [yii\web\HttpException:400] exception 'yii\web\BadRequestHttpException' with m ...

  5. 217&period; Contains Duplicate(C&plus;&plus;)

    217. Contains Duplicate Given an array of integers, find if the array contains any duplicates. Your ...

  6. 二维码闪电登录流程详解,附demo(1&sol;2)

    二维码,最早发明于日本,它是用某种特定的几何图形按一定规律在平面(二维方向上)分布的黑白相间的图形记录数据符号信息的,使用若干个与二进制相对应的几何形体来表示文字数值信息,通过图象输入设备或光电扫描设 ...

  7. Python2&period;&ast;与Python3&period;&ast;共存问题

    安装Python 2.7后,本来在3.4下能正常使用的脚本无法运行.网上有的方法是把两个版本的主程序分别改名为python2和python3,人眼判断脚本,手输命令行执行脚本.像我这样喜欢双击.拖拽的 ...

  8. python 发送带附件的邮件

    特别注意的地方:filespart.add_header("Content-Disposition","attachment",filename=file_na ...

  9. node-sass 安装

    设置 export ELECTRON_MIRROR="https://npm.taobao.org/mirrors/electron/" export SASS_BINARY_SI ...

  10. python josn转换方法-字典

    python_json常用的方法 1. 什么是JSON? JSON 可以将 JavaScript 对象中表示的一组数据转换为字符串,然后就可以在函数之间轻松地传递这个字符串,或者在异步应用程序中将字符 ...