题目地址:CF1153C Serval and Parenthesis Sequence
思路:贪心
如果有解,那么 \(s_0 = (\) && \(s_{n-1} = )\) && \(n % 2 = 0\) 。
如果有解,那么 \(s_1\) ~ \(s_{n-2}\) 为一个合法的括号序列。
那么已知的 \((\) 和 \()\) 个数不能超过一半
接下来贪心:如果有解,那么一定有一组解是把 \(?\) 中左边一部分填成 \((\) ,右边一部分填成 \()\) ,且保证 \((\) 和 \()\) 个数正好为一半
那么就这样填呗
填完之后扫一遍是否合法就完了
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 6;
int n, c1, c2, v[N], mn = 1e9;
string s;
int main() {
ios::sync_with_stdio(0);
cin >> n;
cin >> s;
if (s[0] == '?') s[0] = '(';
if (s[n-1] == '?') s[n-1] = ')';
if (s[0] != '(' || s[n-1] != ')') {
puts(":(");
return 0;
}
if (n & 1) {
puts(":(");
return 0;
}
if (n == 2) {
cout << s << endl;
return 0;
}
for (int i = 1; i < n - 1; i++) {
if (s[i] == '(') ++c1;
if (s[i] == ')') ++c2;
}
if (c1 + 1 > n / 2 || c2 + 1 > n / 2) {
puts(":(");
return 0;
}
for (int i = 1; i < n - 1; i++) {
if (s[i] == '?') {
if (c1 + 1 < (n >> 1)) {
++c1;
s[i] = '(';
} else {
++c2;
s[i] = ')';
}
}
}
int x = 0;
for (int i = 1; i < n - 1; i++) {
if (s[i] == '(') x++;
else {
x--;
if (x < 0) {
puts(":(");
return 0;
}
}
}
cout << s << endl;
return 0;
}
CF1153C Serval and Parenthesis Sequence的更多相关文章
-
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 ...
-
cf-Round551-Div2-C. Serval and Parenthesis Sequence(贪心)
题目链接:http://codeforces.com/contest/1153/problem/C 题意:给定由'(',')','?'组成的字符串,问是否能将其中的?全部换成'(‘,’)'使得字符串的 ...
-
Serval and Parenthesis Sequence CodeForces - 1153C
题目大意:一个字符串只含有? ( ),?可以变成 ) 或者 ( ,将字符串中所有的?变成) 或者 ( 使得字符串合法. 合法就是让括号配对,并且不可以提前结束比如:()()这样是不合法的. 题解:既然 ...
-
codeforces 1153 D
cf-551-div2-D C. Serval and Parenthesis Sequence 题意:给定由'(',')','?'组成的字符串,问是否能将其中的?全部换成'(‘,’)'使得字符串的任 ...
-
【Codeforces】Codeforces Round #551 (Div. 2)
Codeforces Round #551 (Div. 2) 算是放弃颓废决定好好打比赛好好刷题的开始吧 A. Serval and Bus 处理每个巴士最早到站且大于t的时间 #include &l ...
-
Codeforces Round #551 (Div. 2) A-E
A. Serval and Bus 算出每辆车会在什么时候上车, 取min即可 #include<cstdio> #include<algorithm> #include< ...
-
Codeforces Round #551 (Div. 2) A~E题解
突然发现上一场没有写,那就补补吧 本来这场应该5题的,结果一念之差E fail了 A. Serval and Bus 基本数学不解释,假如你没有+1 -1真的不好意思见人了 #include<c ...
随机推荐
-
XMl各种格式转换功能代码
package com.cdv.test; import java.io.ByteArrayOutputStream; import java.io.File; import java.io.File ...
-
函数fsp_get_space_header
/**********************************************************************//** Gets a pointer to the sp ...
-
target与currentTarget的区别?
通俗易懂的说法: 比如说现在有A和B, A.addChild(B) A监听鼠标点击事件 那么当点击B时,target是B,currentTarget是A 也就是说,currentTarget始终是监听 ...
-
2017CCPC 网络选拔赛1003 Ramsey定理
Ramsey定理 任意6个人中,一定有三个人互为朋友,或者互相不是朋友. 证明 这里我就不证明了.下面链接有证明 鸽巢原理 Ramsey定理 AC代码 #include <stdio.h> ...
-
UOJ219 NOI2016 优秀的拆分 二分、字符串哈希
传送门 题目可以转化为求\(AA\)的数量,设\(cnt1_x\)表示左端点为\(x\)的\(AA\)的数量,\(cnt2_x\)表示右端点为\(x\)的\(AA\)的数量,那么答案就是\(\sum ...
-
golang json用法讲解
简介 json格式可以算我们日常最常用的序列化格式之一了,Go语言作为一个由Google开发,号称互联网的C语言的语言,自然也对JSON格式支持很好.但是Go语言是个强类型语言,对格式要求极其严格而J ...
-
Codeforces 792B. Counting-out Rhyme
B. Counting-out Rhyme time limit per test: 1 second memory limit per test: 256 megabytes input: stan ...
-
PHP使用mysqli扩展连接MySQL数据库
这篇文章主要介绍了PHP使用mysqli扩展连接MySQL数据库,需要的朋友可以参考下 1.面向对象的使用方式 $db = new mysqli('localhost', 'root', '12345 ...
-
自定义AngularJS中的services服务
<!DOCTYPE html><html><head><meta http-equiv="Content-Type" content=&q ...
-
Python之‘’控制流‘’
一.if语句 格式: i1 = 3 if i1 > 4: print('yes you are right') elif 0 < i1 < 4: print('im dont kon ...