贪心+构造,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,右括号当成-1 那么只要任意前缀非负且最终总和为0那么该括号序列就是合法 对于本题&…...
网络安全等级保护基本要求 第1部分:安全通用要求
基本要求 第三级 安全物理环境 物理位置选择 a) 机房场地应选择在具有防震、防风和防雨等能力的建筑内; b) 机房场地应避免设在建筑物的顶层或地下室,否则应加强防水和防潮措施 物理访问控制 a) 机房出入口应配置电子门禁系统,控制、鉴…...
ubuntu22.04防火墙策略
1. 安装和配置UFW 1.1 安装UFW 如果UFW尚未安装,可以使用以下命令进行安装: sudo apt update sudo apt install ufw1.2 启用UFW 启用UFW并允许SSH流量,以防止自己被锁定在系统之外: sudo ufw allow OpenSSH sudo ufw enable2…...
selenium的使用教程
Selenium简介 Selenium是一个用于Web应用程序自动化测试工具。它支持多种浏览器,可以录制、编辑和运行自动化测试。通过Selenium,我们可以编写脚本来模拟用户在浏览器中的操作,从而进行功能测试。 二、安装与配置 安装Selenium库 使用pip安…...
Centos: ifconfig command not found且ip addr查不到服务器IP
前段时间部门新派发了服务器,让我过去使用U盘装机,装完后使用ifconfig查不到服务器IP地址,ip addr也是查不到 ifconfig:command not found (这两个图片先用虚拟机的替代一下) 在网上找资料(CSDN,博客园,知乎…...
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 多选框
何时使用 在一组可选项中进行多项选择时; 单独使用可以表示两种状态之间的切换,和 switch 类似。区别在于切换 switch 会直接触发状态改变,而 checkbox 一般用于状态标记,需要和提交操作配合。 案例:多选框组件 核心…...
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开发一个笔记本电脑是否在充电的小工具
笔记本充电状态有两种监测方式,一种是主动查询,另一种是注册充电状态变化事件 1,先说主动监控吧,建立一个线程,反复查询SystemInformation.PowerStatus.PowerLineStatus private void readPower(){while (true){this.…...
构建汛期智慧水利新生态:EasyCVR视频汇聚监控综合管理方案解析
一、项目背景与目标 随着我国水利事业的不断发展,水利设施的管理与维护工作愈发重要。随着夏季汛期的到来,水利管理工作面临着巨大的挑战。为确保水利设施的安全运行,及时应对可能出现的汛情,建设一套高效、智能的视频监控可视化…...
linux中HADOOP_HOME和JAVA_HOME删除后依然指向旧目录
在Linux系统中,当你删除了HADOOP_HOME和JAVA_HOME环境变量后,它们依然指向旧目录,可能是因为这些变量在其他地方被设置了。以下是一些常见的原因和解决方法: 系统级配置文件: 检查系统级的环境变量配置文件,如/etc/profile、/etc/bashrc、/etc/environment,以及/etc/pro…...
C++中的结构体——结构体案例1_2
案例描述 学校正在做毕设项目,每位老师指导5名学生,总共有3名老师,需求如下 设计学生和老师的结构体,其中在老师的结构体中,有老师的姓名和一个存放5名学生的数组作为成员 学生的成员有姓名、考试分数,创…...
python接入汇率换算工具提高网站/小程序日活度
实时汇率换算工具可以帮助用户快速准确地计算不同货币之间最新的汇兑比例。无论是金融从业者或者是人们日常生活出行都会使用到,广泛用于国际结算、银行汇率查询应用、开展跨国贸易、投资等参考场景。 我们可以通过在网站或者小程序中接入这样一个小工具࿰…...
Ubuntu 网络重置
在 Ubuntu 中,如果遇到可以联网但是无法打开许多网页的问题,这可能是 DNS 设置不正确或者网络配置有误引起的。重置网络配置到默认设置可以帮助解决这类问题。以下是几种方法来重置 Ubuntu 的网络配置: ### 1. 重启网络服务 有时候简单地重启…...
防护DDoS攻击出现的常见误区
很多运维人员会通过自己的一些方式来缓解DDoS攻击,但效果却并不明显,今天蔡蔡就来说说防护DDoS攻击最容易出现哪些误区? 误区一:通过CDN防御DDoS攻击 经常有人认为高防IP这么贵,为什么不用几百块的CDN来预防DDoS&…...
入门 Axure RP 9 | 原型设计基础教程
选择正确的原型设计工具并非易事,Axure RP 9能够快速完成原型设计。原型设计是一种经过时间考验的方法,可以将你的设计快速放置在用户的设备并交到他们手中。替代Axure RP 9的原型设计工具即时设计是一个完全集成的协同设计工具,无需使用不同…...
一线大厂都在高薪抢AI产品经理?
哈喽,大家下午好呀~ 当AI的风吹到产品届,唯叹相见恨晚! 作为一名产品经理,日常写调研、需求分析、产品设计、项目管理、数据分析……每一项工作都需要投入大量的时间和精力。 但用上AI后,你会发现写个需…...
html实现粘贴excel数据,在页面表格中复制
录入数据时,有时候需要把excel中的数据一条条粘贴到页面中,当数据量过多时,这种操作很令人崩溃。本篇文章实现了从excel复制好多行数据后,可在页面粘贴的功能 具体实现代码 <!DOCTYPE html> <html lang"en"> <head…...
WPF视频学习-简单应用篇图书馆程序(一)
1.登录界面和主界面跳转 先把登录界面分为三行《Grid》 先添加两行: <Grid><!--//分三行,行排列--><Grid.RowDefinitions><RowDefinition Height"auto"/><RowDefinition Height"auto"/><RowDef…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
redis和redission的区别
Redis 和 Redisson 是两个密切相关但又本质不同的技术,它们扮演着完全不同的角色: Redis: 内存数据库/数据结构存储 本质: 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能: 提供丰…...


