cf1750E Bracket Cost
前言:
好久没训练了,来做道计数题找找感觉。**期末毁我青春
大意:
定义对于一个括号串 s的值,为通过最小次数以下操作使 s 实现括号匹配的操作次数。
- 选择一个子串,循环右移一位。
- 在任意一个位置插入一个任意括号。
求一个括号串的所有非空子串的值的和。
思路:
显然先分析对于一个串的情况
不难发现,操作1其实就是把子串的末尾提到前面,对于其它的字符不会有任何影响
我们令L表示串内左括号的数量,R表示右括号的数量,x表示串内已经匹配的括号对的数量
然后这里就有一个比较显然的操作思路:
假定L>=R,对于每一个没有匹配的左括号,如果我们能找到一个尚未匹配的右括号,则它一定在该左括号的前面,所以我们直接取以它们为端点的字串,执行操作1,这就实现了一个匹配。由于操作一只会对字串的端点产生影响,所以这不会破坏任何已有结构。如果这个左括号找不到尚未匹配的右括号,我们就直接执行操作2即可。
注意到每次操作都不会浪费,都达到了对应操作所能消去的最多的括号数,所以该操作是最优的,此时总操作次数是L-x
同理,R>=L时,总操作次数就是R-x
总结一下,对于一个字符串,其操作此时就是max{L,R}-1
所以我们得到答案就是
先求x
很套路地考虑每一个匹配的贡献,有多少个字串可以包含它。取左端点l,右端点r,则贡献就是l*(n-r+1),整体用一个栈就能实现匹配+求和的过程了
考虑max(L,R),可以做如下转化:,L+R的求和是比较简单的,就是类似于上一个的求法,考虑每一个位置的贡献。|L-R|,其实就是区间和的绝对值
取sum表示字符串的前缀和(左括号取1,右括号取-1),对sum排序之后(注意要把sum0也加进去)
不难发现这个的求和可以转化为
也就是
两部分求完之后除以2即可
整体时间复杂度nlogn
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define endl '\n'
const ll N=2e5+10;
ll n;
string s;
ll sum[N];
void solve()
{cin>>n;for(int i=0;i<=n+5;++i) sum[i]=0;cin>>s;s=" "+s;for(int i=1;i<=n;++i){if(s[i]=='(') sum[i]=sum[i-1]+1;else sum[i]=sum[i-1]-1;}sort(sum,sum+1+n);ll tot=0;for(int i=1;i<=n;++i) tot+=i*(n-i+1);for(int i=1;i<=n;++i) tot+=i*sum[i];for(int i=0;i<=n-1;++i) tot-=(n-i)*sum[i];tot/=2;//cout<<tot<<' ';stack<ll> st;for(int i=1;i<=n;++i){if(s[i]=='(') st.push(i);else{if(st.empty()) continue;int id=st.top();tot-=id*(n-i+1);st.pop();}}cout<<tot<<endl;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll t;cin>>t;while(t--)solve();return 0;
}
相关文章:
cf1750E Bracket Cost
前言: 好久没训练了,来做道计数题找找感觉。**期末毁我青春 大意: 定义对于一个括号串 s的值,为通过最小次数以下操作使 s 实现括号匹配的操作次数。 选择一个子串,循环右移一位。在任意一个位置插入一个任意括号。 求一个括…...
Vue+springboot医院住院挂号登记收费系统7ui9s
医院信息管理系统的开发过程中,采用B / S架构,主要使用java语言进行开发,结合最新流行的springboot框架。使用Mysql数据库和idea开发环境。该医院信息管理系统包括用户、医生和管理员。其主要功能包括用户管理、医生管理、医生信息管理、预约…...
大前端之Koa2学习
Koa2框架介绍 Koa2是一个基于Node.js的Web框架,它使用了ES6的语法和async/await特性,使得编写异步代码更加简单和优雅。Koa2的核心思想是中间件,它允许开发者将应用程序拆分成小的、可重用的部分,从而使得代码更加模块化和易于维…...
Qml实现Dock浮动、停靠功能
纯Qml实现Dock浮动、停靠功能 效果展示github地址:介绍环境Demo代码参数说明API说明 效果展示 Qml Dock效果演示 github地址: https://github.com/longtwilight/QmlDock 介绍 这是一个使用纯qml实现的Dock组件,它支持停靠、浮动、窗体分离、窗体独立、大小调整等…...
最新版本 Stable Diffusion 开源 AI 绘画工具之微调模型篇
✨ 目录 🎈 模型种类🎈 变分自动编码器 / VAE🎈 美学梯度 / Aesthetic Gradients🎈 大型语言模型的低阶自适应 / LoRA🎈 超网络模型 / Hypernetwork🎈 微调模型 / LyCORIS 🎈 模型种类 当你打开…...
路径规划算法:基于哈里斯鹰优化的路径规划算法- 附代码
路径规划算法:基于哈里斯鹰优化的路径规划算法- 附代码 文章目录 路径规划算法:基于哈里斯鹰优化的路径规划算法- 附代码1.算法原理1.1 环境设定1.2 约束条件1.3 适应度函数 2.算法结果3.MATLAB代码4.参考文献 摘要:本文主要介绍利用智能优化…...
Web 应用程序防火墙 (WAF) 相关知识介绍
Web应用程序防火墙 (WAF) 如何工作? Web应用防护系统(也称为:网站应用级入侵防御系统。英文:Web Application Firewall,简称:WAF)。利用国际上公认的一种说法:Web应用防火墙是通过执…...
docker快速部署hue+hue集成hive
首先需要安装hive,hive的安装在HIVE的安装与配置_EEEurekaaa!的博客-CSDN博客 安装完成之后,使用脚本命令启动hdfs和hive的相关服务。 一、安装docker # 安装yum-config-manager配置工具 $ yum -y install yum-utils # 设置yum源 $ yum-co…...
基于java SpringBoot和Vue uniapp的校园信息交流小程序
随着信息社会的网络化和计算机科学的广泛普及和迅速普及应用,具有综合智能的我国校园信息教育网络已成为推动中小学科学教育及其实践科学发展的信息技术手段。迅速推进了信息化改革,改善了高校信息交流的网络环境,提高了信息教育平台的管理水…...
数据包伪造替换、会话劫持、https劫持之探索和测试
(一)数据包替换攻击 该攻击过程如下:伪造服务器响应客户端的数据包。监听客户端的数据包,用预先伪造的数据包,伪装成服务器返回的数据发送给客户端。 因为攻击者跟目标在同一个局域网,所以攻击者发送的数…...
正则表达式集合
目录 一、校验数字的表达式 1. 数字 2. n位的数字 3. 至少n位的数字 4. m-n位的数字 5. 零和非零开头的数字 6. 非零开头的最多带两位小数的数字 7. 带1-2位小数的正数或负数 8. 正数、负数、和小数 9. 有两位小数的正实数 10. 有1~3位小数的正实数 11. 非零的正整…...
Django框架中models对象转换为json的方法
在django框架中输出api接口时一般都是输出json数据但是通过orm获取的数据库数据一般都是object所以需要转换成json数据,一般有一下3种情况 1.models对象使用“all()”时 from django.http import HttpResponse from django.core import serializers from TestMode…...
利用Servlet编写第一个“hello world“
利用Servlet编写第一个"hello world" 🔎创建 Maven 项目🔎引入依赖🔎创建目录🔎编写代码🔎打包代码🔎部署🔎程序验证🔎结尾 🔎创建 Maven 项目 Maven 是一个构…...
python 爬虫之js逆向爬虫详解
随着网站前端技术的不断发展,越来越多的网站采用JS进行渲染,并加上了一些反爬机制,导致传统的爬虫技术有些力不从心。本文将为大家介绍如何进行JS逆向爬虫,并且不少于1000字。 一、JS逆向爬虫的介绍 JS逆向是一种分析反爬机制的…...
SpringBoot:WebSocket实现消息撤回、图片撤回
下面只是讲述一下实现思路,代码基本没有哈!有时间单独发表一篇关于websocket的相关操作的博客。 1. 消息撤回、图片撤回 个人觉得关于撤回,需要下述几个过程: 发送的消息的标签上可以定义一个属性,这个属性的值应该是…...
输出指定日期区间内的所有天、周、月
部分方法需要依赖hutool工具包。 <dependency><groupId>cn.hutool</groupId><artifactId>hutool-all</artifactId><version>4.5.10</version> </dependency>需求:输出2023-04-17到2023-05-23期间所有的天、周、月。…...
【线性规划模型】
线性规划模型:原理介绍和预测应用 引言 线性规划是运筹学中一种重要的数学优化方法,被广泛应用于各个领域,包括工业、经济、物流等。 线性规划模型的原理 线性规划模型的目标是在一组线性约束条件下,寻找一组变量的最优解&…...
android 12.0卸载otg设备开机不加载otg设备
1.概述 在12.0定制化开发过程中,客户有功能需求,通过系统属性值控制是否加载挂载otg设备,当设置为卸载模式时,要求不能挂载otg设备,开机也不能挂载otg设备 2.卸载otg设备开机不加载otg设备的核心代码 frameworks/base/services/core/java/com/android/server/StorageMan…...
通过 Wacom 的 Project Mercury 提高远程办公效率
过去几年中,我们的工作方式发生了翻天覆地的变化。疫情加快了对远程办公和协作的采纳,导致人们更加依赖技术来联系团队和提高工作效率。 但是,那些依靠专门硬件和软件来完成工作的创作者呢?艺术家、设计师和开发人员需要使用专门…...
Linux-0.11 文件系统namei.c详解
Linux-0.11 文件系统namei.c详解 模块简介 namei.c是整个linux-0.11版本的内核中最长的函数,总长度为700行。其核心是namei函数,即根据文件路径寻找对应的i节点。 除此以外,该模块还包含一些创建目录,删除目录,创建目…...
bilibili-api完全指南:评论数据爬取的4个突破式解决方案
bilibili-api完全指南:评论数据爬取的4个突破式解决方案 【免费下载链接】bilibili-api 哔哩哔哩常用API调用。支持视频、番剧、用户、频道、音频等功能。原仓库地址:https://github.com/MoyuScript/bilibili-api 项目地址: https://gitcode.com/gh_mi…...
手把手教你用Claude Desktop的MCP协议,5分钟搞定本地SQLite数据库查询
5分钟实现自然语言查询SQLite:Claude Desktop MCP协议实战指南 想象一下这样的场景:你手头有一个存储着上万条商品信息的SQLite数据库,现在需要快速统计某个品类的库存数量。传统方式可能需要打开数据库工具、编写SQL查询语句,或者…...
颠覆传统投资分析:TradingAgents-CN智能交易系统零门槛部署指南
颠覆传统投资分析:TradingAgents-CN智能交易系统零门槛部署指南 【免费下载链接】TradingAgents-CN 基于多智能体LLM的中文金融交易框架 - TradingAgents中文增强版 项目地址: https://gitcode.com/GitHub_Trending/tr/TradingAgents-CN 在金融科技迅猛发展的…...
好写作AI:利用多轮人机交互迭代实现深度降AIGC的方法论
改一遍不够?那就改三遍——但每遍都要改对地方很多同学用AI辅助写论文,流程是这样的:用AI生成一段文字 → 觉得“AI味儿”有点重 → 手动改几个词 → 提交。然后被检测系统打回来。于是困惑:我都改了,怎么还是不行&…...
开发者的第二曲线:2026年最赚钱的5个技术副业
在技术范式加速重构的2026年,软件质量保障的重要性已从“成本中心”跃升为“价值中心”。对于敏锐的软件测试从业者而言,这不仅是职业的深化,更是将专业壁垒转化为财富增长的绝佳契机。传统的“接私活”模式正在被更具复利效应和杠杆价值的“…...
告别格式枷锁:ncmdumpGUI让音乐自由播放变得触手可及
告别格式枷锁:ncmdumpGUI让音乐自由播放变得触手可及 【免费下载链接】ncmdumpGUI C#版本网易云音乐ncm文件格式转换,Windows图形界面版本 项目地址: https://gitcode.com/gh_mirrors/nc/ncmdumpGUI 开篇痛点直击:那些被NCM格式困住的…...
GLM-4.1V-9B-Base效果展示:艺术画作风格+主题+文化元素三重解析
GLM-4.1V-9B-Base效果展示:艺术画作风格主题文化元素三重解析 1. 视觉理解新标杆:GLM-4.1V-9B-Base简介 GLM-4.1V-9B-Base是智谱开源的一款视觉多模态理解模型,专为图像内容识别、场景描述和目标问答任务而设计。不同于普通的图像识别工具&…...
嵌入式AI新篇章:Qwen3-ASR-0.6B在边缘计算设备上的部署与优化
嵌入式AI新篇章:Qwen3-ASR-0.6B在边缘计算设备上的部署与优化 1. 引言:当语音识别遇见边缘计算 想象一下,你对着一个巴掌大的智能音箱说话,它几乎在你话音落下的瞬间就理解了你的意思,并且完全不需要连接云端。或者&…...
别再只用柱状图了!用Python的Matplotlib画个酷炫的雷达图,5分钟搞定你的个人技能展示
用Python打造专业级技能雷达图:5步提升你的职场竞争力 简历上那些千篇一律的柱状图和百分比条已经让招聘官审美疲劳了?试试用Matplotlib绘制一个令人眼前一亮的雷达图来展示你的核心技能组合。这种可视化方式不仅能清晰呈现你在各个领域的熟练程度&#…...
TTL门电路在现代数字设计中的应用:从基础到OC门实战
TTL门电路在现代数字设计中的应用:从基础到OC门实战 在数字电路设计的工具箱里,TTL(晶体管-晶体管逻辑)门电路就像瑞士军刀一样经典而实用。尽管CMOS技术如今占据主流,但TTL在特定场景下依然展现出独特的优势。特别是在…...
