当前位置: 首页 > news >正文

贪心+构造,CF1153 C. Serval and Parenthesis Sequence

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 1153C - Codeforces


二、解题报告

1、思路分析

对于括号匹配问题我们经典做法是左括号当成1,右括号当成-1

那么只要任意前缀非负且最终总和为0那么该括号序列就是合法

对于本题,由于我们要保证任意前缀都不合法,所以任意严格前缀和都是正数(如果出现负数那么说明非法,如果为0则不满足本题要求)

所以前缀和要尽可能大

我们把'?’当成-1,预处理后缀和

遍历序列,如果当前sum + suf[i] < 0,说明我们还需添加左括号

否则添加右括号

如果中途存在sum <= 0且i != n -1说明非法

最后输出前如果sum != 0也说明无解

2、复杂度

时间复杂度: O(N)空间复杂度:O(N)

3、代码详解

 ​
#include <bits/stdc++.h>
using i64 = long long;
using i128 = __int128;
using PII = std::pair<int, int>;std::ostream& operator<< (std::ostream& out, i128 x) {std::string s;while (x) s += ((x % 10) ^ 48), x /= 10;std::reverse(s.begin(), s.end());return out << s;
}void solve() {int N;std::string s;std::cin >> N >> s;if (N & 1) {std::cout << ":(";return;}std::vector<int> suf(N + 1);std::unordered_map<char, int> mp;mp['('] = 1, mp[')'] = -1, mp['?'] = -1;for (int i = N - 1; ~i; i -- ) suf[i] = suf[i + 1] + mp[s[i]];int sum = 0;for (int i = 0; i < N; i ++ ) {if (s[i] == '?') {if (sum + suf[i] < 0) sum ++, s[i] = '(';else sum --, s[i] = ')';}else sum += mp[s[i]];if (sum <= 0 && i + 1 < N) {std::cout << ":(";return;}}if (!sum) std::cout << s;else std::cout << ":(";
}   int main(int argc, char** argv) {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int _ = 1;// std::cin >> _;while (_ --)solve();return 0;
}

相关文章:

贪心+构造,CF1153 C. Serval and Parenthesis Sequence

一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 Problem - 1153C - Codeforces 二、解题报告 1、思路分析 对于括号匹配问题我们经典做法是左括号当成1&#xff0c;右括号当成-1 那么只要任意前缀非负且最终总和为0那么该括号序列就是合法 对于本题&…...

网络安全等级保护基本要求 第1部分:安全通用要求

基本要求 第三级 安全物理环境 物理位置选择 a) 机房场地应选择在具有防震、防风和防雨等能力的建筑内&#xff1b; b) 机房场地应避免设在建筑物的顶层或地下室&#xff0c;否则应加强防水和防潮措施 物理访问控制 a) 机房出入口应配置电子门禁系统&#xff0c;控制、鉴…...

ubuntu22.04防火墙策略

1. 安装和配置UFW 1.1 安装UFW 如果UFW尚未安装&#xff0c;可以使用以下命令进行安装&#xff1a; sudo apt update sudo apt install ufw1.2 启用UFW 启用UFW并允许SSH流量&#xff0c;以防止自己被锁定在系统之外&#xff1a; sudo ufw allow OpenSSH sudo ufw enable2…...

selenium的使用教程

Selenium简介 Selenium是一个用于Web应用程序自动化测试工具。它支持多种浏览器&#xff0c;可以录制、编辑和运行自动化测试。通过Selenium&#xff0c;我们可以编写脚本来模拟用户在浏览器中的操作&#xff0c;从而进行功能测试。 二、安装与配置 安装Selenium库 使用pip安…...

Centos: ifconfig command not found且ip addr查不到服务器IP

前段时间部门新派发了服务器&#xff0c;让我过去使用U盘装机&#xff0c;装完后使用ifconfig查不到服务器IP地址&#xff0c;ip addr也是查不到 ifconfig&#xff1a;command not found (这两个图片先用虚拟机的替代一下) 在网上找资料(CSDN&#xff0c;博客园&#xff0c;知乎…...

WPF学习(2)--类与类的继承2-在窗口的实现

一、代码分析 1.Animal.cs 1.1 代码 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;namespace AnimalNamespace {public class Animal{public string Name { get; set; }public int Age { get; set…...

Docker面试整理-Docker容器与虚拟机比较,安全性如何?

Docker 容器与传统的虚拟机(VM)在许多方面都不同,其中之一是安全性。每种技术都有其特定的安全特点和潜在的风险。了解这些差异可以帮助你做出更好的决策,适当地使用它们来保障系统安全。 容器与虚拟机的安全性对比: 1. 隔离性: ● 虚拟机:提供较高的隔离性。每个虚拟机…...

Python私教张大鹏 Vue3整合AntDesignVue之Checkbox 多选框

何时使用 在一组可选项中进行多项选择时&#xff1b; 单独使用可以表示两种状态之间的切换&#xff0c;和 switch 类似。区别在于切换 switch 会直接触发状态改变&#xff0c;而 checkbox 一般用于状态标记&#xff0c;需要和提交操作配合。 案例&#xff1a;多选框组件 核心…...

flutter 导出iOS问题3

更新flutter版本后 macminihaomacMiniaodeMini SocialIM % flutter --version Flutter 3.7.12 • channel stable • https://github.com/flutter/flutter.git Framework • revision 4d9e56e694 (1 year, 2 months ago) • 2023-04-17 21:47:46 -0400 Engine • revision 1a6…...

用winform开发一个笔记本电脑是否在充电的小工具

笔记本充电状态有两种监测方式&#xff0c;一种是主动查询&#xff0c;另一种是注册充电状态变化事件 1&#xff0c;先说主动监控吧&#xff0c;建立一个线程&#xff0c;反复查询SystemInformation.PowerStatus.PowerLineStatus private void readPower(){while (true){this.…...

构建汛期智慧水利新生态:EasyCVR视频汇聚监控综合管理方案解析

一、项目背景与目标 随着我国水利事业的不断发展&#xff0c;水利设施的管理与维护工作愈发重要。随着夏季汛期的到来&#xff0c;水利管理工作面临着巨大的挑战。为确保水利设施的安全运行&#xff0c;及时应对可能出现的汛情&#xff0c;建设一套高效、智能的视频监控可视化…...

linux中HADOOP_HOME和JAVA_HOME删除后依然指向旧目录

在Linux系统中,当你删除了HADOOP_HOME和JAVA_HOME环境变量后,它们依然指向旧目录,可能是因为这些变量在其他地方被设置了。以下是一些常见的原因和解决方法: 系统级配置文件: 检查系统级的环境变量配置文件,如/etc/profile、/etc/bashrc、/etc/environment,以及/etc/pro…...

C++中的结构体——结构体案例1_2

案例描述 学校正在做毕设项目&#xff0c;每位老师指导5名学生&#xff0c;总共有3名老师&#xff0c;需求如下 设计学生和老师的结构体&#xff0c;其中在老师的结构体中&#xff0c;有老师的姓名和一个存放5名学生的数组作为成员 学生的成员有姓名、考试分数&#xff0c;创…...

python接入汇率换算工具提高网站/小程序日活度

实时汇率换算工具可以帮助用户快速准确地计算不同货币之间最新的汇兑比例。无论是金融从业者或者是人们日常生活出行都会使用到&#xff0c;广泛用于国际结算、银行汇率查询应用、开展跨国贸易、投资等参考场景。 我们可以通过在网站或者小程序中接入这样一个小工具&#xff0…...

Ubuntu 网络重置

在 Ubuntu 中&#xff0c;如果遇到可以联网但是无法打开许多网页的问题&#xff0c;这可能是 DNS 设置不正确或者网络配置有误引起的。重置网络配置到默认设置可以帮助解决这类问题。以下是几种方法来重置 Ubuntu 的网络配置&#xff1a; ### 1. 重启网络服务 有时候简单地重启…...

防护DDoS攻击出现的常见误区

很多运维人员会通过自己的一些方式来缓解DDoS攻击&#xff0c;但效果却并不明显&#xff0c;今天蔡蔡就来说说防护DDoS攻击最容易出现哪些误区&#xff1f; 误区一&#xff1a;通过CDN防御DDoS攻击 经常有人认为高防IP这么贵&#xff0c;为什么不用几百块的CDN来预防DDoS&…...

入门 Axure RP 9 | 原型设计基础教程

选择正确的原型设计工具并非易事&#xff0c;Axure RP 9能够快速完成原型设计。原型设计是一种经过时间考验的方法&#xff0c;可以将你的设计快速放置在用户的设备并交到他们手中。替代Axure RP 9的原型设计工具即时设计是一个完全集成的协同设计工具&#xff0c;无需使用不同…...

一线大厂都在高薪抢AI产品经理?

哈喽&#xff0c;大家下午好呀&#xff5e; 当AI的风吹到产品届&#xff0c;唯叹相见恨晚&#xff01; 作为一名产品经理&#xff0c;日常写调研、需求分析、产品设计、项目管理、数据分析……每一项工作都需要投入大量的时间和精力。 但用上AI后&#xff0c;你会发现写个需…...

html实现粘贴excel数据,在页面表格中复制

录入数据时&#xff0c;有时候需要把excel中的数据一条条粘贴到页面中&#xff0c;当数据量过多时&#xff0c;这种操作很令人崩溃。本篇文章实现了从excel复制好多行数据后,可在页面粘贴的功能 具体实现代码 <!DOCTYPE html> <html lang"en"> <head…...

WPF视频学习-简单应用篇图书馆程序(一)

1.登录界面和主界面跳转 先把登录界面分为三行《Grid》 先添加两行&#xff1a; <Grid><!--//分三行&#xff0c;行排列--><Grid.RowDefinitions><RowDefinition Height"auto"/><RowDefinition Height"auto"/><RowDef…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...