题目链接: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(贪心)的更多相关文章
-
CF1153C Serval and Parenthesis Sequence
题目地址:CF1153C Serval and Parenthesis Sequence 思路:贪心 如果有解,那么 \(s_0 = (\) && \(s_{n-1} = )\) &a ...
-
C. Serval and Parenthesis Sequence 【括号匹配】 Codeforces Round #551 (Div. 2)
冲鸭,去刷题:http://codeforces.com/contest/1153/problem/C C. Serval and Parenthesis Sequence time limit pe ...
-
Serval and Parenthesis Sequence【思维】
Serval and Parenthesis Sequence 题目链接(点击) Serval soon said goodbye to Japari kindergarten, and began ...
-
cf——C. Serval and Parenthesis Sequence
括号正确匹配问题,应该不难 #include <iostream> #include <cstring> #include <string> #include &l ...
-
Serval and Parenthesis Sequence CodeForces - 1153C
题目大意:一个字符串只含有? ( ),?可以变成 ) 或者 ( ,将字符串中所有的?变成) 或者 ( 使得字符串合法. 合法就是让括号配对,并且不可以提前结束比如:()()这样是不合法的. 题解:既然 ...
-
cf 442 div2 F. Ann and Books(莫队算法)
cf 442 div2 F. Ann and Books(莫队算法) 题意: \(给出n和k,和a_i,sum_i表示前i个数的和,有q个查询[l,r]\) 每次查询区间\([l,r]内有多少对(i, ...
-
HDU5014Number Sequence(贪心)
HDU5014Number Sequence(贪心) 题目链接 题目大意: 给出n,然后给出一个数字串,长度为n + 1, 范围在[0, n - 1].然后要求你找出另外一个序列B,满足上述的要求,而 ...
-
【题解】Cut the Sequence(贪心区间覆盖)
[题解]Cut the Sequence(贪心区间覆盖) POJ - 3017 题意: 给定一大堆线段,问用这些线段覆盖一个连续区间1-x的最小使用线段的数量. 题解 考虑一个这样的贪心: 先按照左端 ...
-
CF 612C. Replace To Make Regular Bracket Sequence【括号匹配】
[链接]:CF [题意]:给你一个只含有括号的字符串,你可以将一种类型的左括号改成另外一种类型,右括号改成另外一种右括号 问你最少修改多少次,才能使得这个字符串匹配,输出次数 [分析]: 本题用到了栈 ...
随机推荐
-
C++中“强制转换”的四大天王
哈哈,这个标题有点搞笑了!笑一笑,十年少,希望大家都嗨心! 在C++中主要有四种强制类型转换:static_cast,reinterpret_cast,const_cast,dynamic_cast. ...
-
门户级UGC系统的技术进化路线——新浪新闻评论系统的架构演进和经验总结(转)
add by zhj:先收藏了 摘要:评论系统是所有门户网站的核心标准服务组件之一.本文作者曾负责新浪网评论系统多年,这套系统不仅服务于门户新闻业务,还包括调查.投票等产品,经历了从单机到多机再到集群 ...
-
spring中配置jndi数据源
spring AplicationContext.xml中的配置 <bean id="dataSource1" class="org.springframewor ...
-
[Yii2]Unable to verify your data submission(你提交的资料无法被验证)
Yii2中,使用form提交数据,会提示: [yii\web\HttpException:400] exception 'yii\web\BadRequestHttpException' with m ...
-
217. Contains Duplicate(C++)
217. Contains Duplicate Given an array of integers, find if the array contains any duplicates. Your ...
-
二维码闪电登录流程详解,附demo(1/2)
二维码,最早发明于日本,它是用某种特定的几何图形按一定规律在平面(二维方向上)分布的黑白相间的图形记录数据符号信息的,使用若干个与二进制相对应的几何形体来表示文字数值信息,通过图象输入设备或光电扫描设 ...
-
Python2.*与Python3.*共存问题
安装Python 2.7后,本来在3.4下能正常使用的脚本无法运行.网上有的方法是把两个版本的主程序分别改名为python2和python3,人眼判断脚本,手输命令行执行脚本.像我这样喜欢双击.拖拽的 ...
-
python 发送带附件的邮件
特别注意的地方:filespart.add_header("Content-Disposition","attachment",filename=file_na ...
-
node-sass 安装
设置 export ELECTRON_MIRROR="https://npm.taobao.org/mirrors/electron/" export SASS_BINARY_SI ...
-
python josn转换方法-字典
python_json常用的方法 1. 什么是JSON? JSON 可以将 JavaScript 对象中表示的一组数据转换为字符串,然后就可以在函数之间轻松地传递这个字符串,或者在异步应用程序中将字符 ...