CF1153C Serval and Parenthesis Sequence

时间:2022-08-29 18:04:51

题目地址: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的更多相关文章

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

  2. Serval and Parenthesis Sequence【思维】

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

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

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

  4. cf-Round551-Div2-C&period; Serval and Parenthesis Sequence(贪心)

    题目链接:http://codeforces.com/contest/1153/problem/C 题意:给定由'(',')','?'组成的字符串,问是否能将其中的?全部换成'(‘,’)'使得字符串的 ...

  5. Serval and Parenthesis Sequence CodeForces - 1153C

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

  6. codeforces 1153 D

    cf-551-div2-D C. Serval and Parenthesis Sequence 题意:给定由'(',')','?'组成的字符串,问是否能将其中的?全部换成'(‘,’)'使得字符串的任 ...

  7. 【Codeforces】Codeforces Round &num;551 &lpar;Div&period; 2&rpar;

    Codeforces Round #551 (Div. 2) 算是放弃颓废决定好好打比赛好好刷题的开始吧 A. Serval and Bus 处理每个巴士最早到站且大于t的时间 #include &l ...

  8. Codeforces Round &num;551 &lpar;Div&period; 2&rpar; A-E

    A. Serval and Bus 算出每辆车会在什么时候上车, 取min即可 #include<cstdio> #include<algorithm> #include&lt ...

  9. Codeforces Round &num;551 &lpar;Div&period; 2&rpar; A~E题解

    突然发现上一场没有写,那就补补吧 本来这场应该5题的,结果一念之差E fail了 A. Serval and Bus 基本数学不解释,假如你没有+1 -1真的不好意思见人了 #include<c ...

随机推荐

  1. XMl各种格式转换功能代码

    package com.cdv.test; import java.io.ByteArrayOutputStream; import java.io.File; import java.io.File ...

  2. 函数fsp&lowbar;get&lowbar;space&lowbar;header

    /**********************************************************************//** Gets a pointer to the sp ...

  3. target与currentTarget的区别?

    通俗易懂的说法: 比如说现在有A和B, A.addChild(B) A监听鼠标点击事件 那么当点击B时,target是B,currentTarget是A 也就是说,currentTarget始终是监听 ...

  4. 2017CCPC 网络选拔赛1003 Ramsey定理

    Ramsey定理 任意6个人中,一定有三个人互为朋友,或者互相不是朋友. 证明 这里我就不证明了.下面链接有证明 鸽巢原理 Ramsey定理 AC代码 #include <stdio.h> ...

  5. UOJ219 NOI2016 优秀的拆分 二分、字符串哈希

    传送门 题目可以转化为求\(AA\)的数量,设\(cnt1_x\)表示左端点为\(x\)的\(AA\)的数量,\(cnt2_x\)表示右端点为\(x\)的\(AA\)的数量,那么答案就是\(\sum ...

  6. golang json用法讲解

    简介 json格式可以算我们日常最常用的序列化格式之一了,Go语言作为一个由Google开发,号称互联网的C语言的语言,自然也对JSON格式支持很好.但是Go语言是个强类型语言,对格式要求极其严格而J ...

  7. Codeforces 792B&period; Counting-out Rhyme

    B. Counting-out Rhyme time limit per test: 1 second memory limit per test: 256 megabytes input: stan ...

  8. PHP使用mysqli扩展连接MySQL数据库

    这篇文章主要介绍了PHP使用mysqli扩展连接MySQL数据库,需要的朋友可以参考下 1.面向对象的使用方式 $db = new mysqli('localhost', 'root', '12345 ...

  9. 自定义AngularJS中的services服务

    <!DOCTYPE html><html><head><meta http-equiv="Content-Type" content=&q ...

  10. Python之&OpenCurlyQuote;’控制流&OpenCurlyQuote;’

    一.if语句 格式: i1 = 3 if i1 > 4: print('yes you are right') elif 0 < i1 < 4: print('im dont kon ...