AtCoder Regular Contest 170(A~B)
A - Yet Another AB Problem
给你两个字符串S和T,你可以对S执行操作,选择两个字符,将前面的改为A,后面的改为B,最少操作几次可以把S改成T。如果改不成就输出-1。
从左往右一个一个改过去,分类讨论,如果是要把A改成B。
S:A->B
T:B
那么T中该位置前面一定要有一个A,否则无法修改。
如果要把B改成A。
S:B->A
T:A
那么T中该位置后面一定要有一个B,否则无法修改。
其中可以本次修改可以更优,即S中后面有一个A,对应T后面的B(一次修改,完成两次对应)
#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define fr first
#define se second
#define endl '\n'
using namespace std;
const int N=2e5+5;int n,ans,a;
string s,t;queue<int>q;
int b[N];void solve(){cin>>n>>s>>t;per(i,0,n-1){if(t[i]=='B' and s[i]=='A')q.push(i);}rep(i,n-1,0){if(t[i]=='B')b[i]++;if(i>=1)b[i-1]=b[i];}per(i,0,n-1){if(t[i]=='A')a++;if(s[i]!=t[i]){if(s[i]=='A'){//需要改成B,前面至少有一个Aif(!a){cout<<-1<<endl;return ;}ans++;}else{//需要改成A,后面至少有一个Bif(!b[i+1]){cout<<-1<<endl;return;}ans++;while(!q.empty() and q.front()<i)q.pop();if(!q.empty()){s[q.front()]='B';q.pop();}}}}cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t=1;while(t--)solve();return 0;
}
补题:B - Arithmetic Progression Subsequence
给你1e5个数,每个数是1~10。对于l和r区间,如果区间中有三个数(不管顺序)a[j],a[k],a[l],满足1 2 3或3 2 1(差为1) 或者1 5 9,9 5 1(差为4)这种差相等的,说明l和r是一个好区间,号区间有几个。
思路1:考虑差值最大只有可能是4,对于一个数a[i],只需要枚举所有差值(sub:1~4),a[i],a[i]+sub,a[i]+2*sub(注意也可以是减法),如果在a[i]之后存在这样的值,那么第三个数的下标及其以后都是好区间。所以只需要想一个算法维护每个数后面的1~10第一次出现的位置。
思路2:找到一个好区间之后就可以无限左右扩展,还需要去判断内部是否有好空间,如果内部有一个好空间,那么外部也都是好空间,所以不应该是从每一个数开始枚举,应该枚举好空间序列长度,从3开始往上扩展。
正确思路:正难则反,只会出现1~10的数,尝试构建无解的情况,从差为0开始往上,如果差重复了就必然有解,如1 1 2 4 8,几乎就没别的数可以填了,就会开始重复了。
AC代码
#include <bits/stdc++.h>
#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define fr first
#define se second
#define endl '\n'
using namespace std;
const int N=1e5+5;int n,a[N],ans;bool check(int l,int r){//约1~100次查询per(i,l,r){per(j,i+1,r){per(k,j+1,r){if(a[j]-a[i]==a[k]-a[j])return true;}}}return false;
}void solve(){cin>>n;per(i,1,n)cin>>a[i];per(i,1,n){per(j,i+1,n){//i和j差到10以内就必然有解,复杂度是带系数的O(n),check比较烂总体约1e9if(check(i,j)){ans+=n-j+1;break;}}}cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t=1;while(t--)solve();return 0;
}
顺带一提不开long long见祖宗。

相关文章:
AtCoder Regular Contest 170(A~B)
A - Yet Another AB Problem 给你两个字符串S和T,你可以对S执行操作,选择两个字符,将前面的改为A,后面的改为B,最少操作几次可以把S改成T。如果改不成就输出-1。 从左往右一个一个改过去,分类讨论&#x…...
rk1126, 实现 yolov8 目标检测
基于 RKNN 1126 实现 yolov8 目标检测 Ⓜ️ RKNN 模型转换 ONNX yolo export model./weights/yolov8s.pt formatonnx导出 RKNN 这里选择输出 concat 输入两个节点 onnx::Concat_425 和 onnx::Concat_426 from rknn.api import RKNNONNX_MODEL ./weights/yolov8s.onnxRKNN_MOD…...
【软件测试】学习笔记-网站可扩展性架构设计
可扩展性,指的是网站的架构设计能够快速适应需求的变化,当需要增加新的功能实现时,对原有架构不需要做修改或者做很少的修改就能够快速实现新的业务需求。 从这个定义中,我们很容易就可以得出衡量网站可扩展性设计优秀与否的主要标…...
深度学习常用代码总结(k-means, NMS)
目录 一、k-means 算法 二、NMS 一、k-means 算法 k-means 是一种无监督聚类算法,常用的聚类算法还有 DBSCAN。k-means 由于其原理简单,可解释强,实现方便,收敛速度快,在数据挖掘、数据分析、异常检测、模式识别、金…...
数据结构·顺序表应用
本节应用是要用顺序表实现一个通讯录,收录联系人的姓名、性别、电话号码、住址、年龄 顺序表的实现在上一节中已经完成了,本节的任务其实就是应用上节写出来的代码的那些接口函数功能,做出来一个好看的,可…...
第一个 OpenGL 程序:旋转的立方体(VS2022 / MFC)
文章目录 OpenGL API开发环境在 MFC 中使用 OpenGL初始化 OpenGL绘制图形重置视口大小 创建 MFC 对话框项目添加 OpenGL 头文件和库文件初始化 OpenGL画一个正方形OpenGL 坐标系改变默认颜色 重置视口大小绘制立方体使用箭头按键旋转立方体深度测试添加纹理应用纹理换一个纹理 …...
剩余银饰的重量 - 华为OD统一考试
OD统一考试(C卷) 分值: 100分 题解: Java / Python / C 题目描述 有N块二手市场收集的银饰,每块银饰的重量都是正整数,收集到的银饰会被熔化用于打造新的饰品。 每一回合,从中选出三块 最重的…...
redis远程连接不上解决办法
问题描述: redis远程服务端运行在192.168.3.90计算机上,客户端计算机(ip:192.168.3.110)通过redsi-cli.exe客户端工具连接时,没有反应,连接不上。 如图所示: 解决步骤: 步骤一&…...
利用Anaconda安装pytorch和paddle深度学习环境+pycharm安装后不能调用pytorch和paddlepaddle框架
问题现象: 之前安装后不能在添加pytorch和paddlepaddle框架 原因(疑似): 在终端中显示pytorch和paddle在C盘但是安装是安装在J盘 解决办法: 卸载、删除文件重新安装后可以看到文件位置在J盘中 但是选择时还是显示C…...
Eclipses安装教程
一、下载开发工具包 1、开发工具包JDK 下载地址链接:https://www.oracle.com/cn/java/technologies/downloads/ 下载教程: 1)点击链接,可以跳转到页面 2)下滑页面,找到开发工具包 3) 记住下载之…...
安装python版opencv的一些问题
安装python版opencv的一些问题 OpenCV是知名的开源计算机视觉算法库,提供了C\Python\Java版共享库。 在Python中使用OpenCV格外简单,一句命令就能安装,一行import就能引入,可谓是神器。然而,在实际使用中可能遇到一些…...
RabbitMQ入门实战
RabbitMQ 是一个开源的消息中间件,实现了高级消息队列协议(AMQP),用于在分布式系统中进行消息传递。它能够在应用之间传递消息,解耦应用组件,提高系统的可伸缩性和可维护性。RabbitMQ 使用高级消息队列协议…...
vue3-模版引用ref
1. 介绍 概念:通过 ref标识 获取真实的 dom对象或者组件实例对象 2. 基本使用 实现步骤: 调用ref函数生成一个ref对象 通过ref标识绑定ref对象到标签 代码如下: 父组件: <script setup> import { onMounted, ref } …...
C# 十大排序算法
以下是常见的十大排序算法(按照学习和实现的顺序排列): 冒泡排序(Bubble Sort)选择排序(Selection Sort)插入排序(Insertion Sort)希尔排序(Shell Sort&…...
面试之Glide如何绑定Activity的生命周期
Glide绑定Activity生命周期 Glide.with() 下面都是它的重载方法,Context,Activity,FragmentActivity, Fragment, android.app.Fragment fragment,View都可以作为他的参数,内容大同小异,都是先getRetriever࿰…...
从 fatal 错误到 sync.Map:Go中 Map 的并发策略
为什么 Go 语言在多个 goroutine 同时访问和修改同一个 map 时,会报出 fatal 错误而不是 panic?我们该如何应对 map 的数据竞争问题呢? 这篇文章将带你一步步了解背后的原理,并引出解决 map 并发问题的方案。 Map 数据竞争 首先…...
Simon算法详解
0.0 Intro 相关的算法: Deutsh-Jozsa算法: 第一个量子算法对经典算法取得指数级加速的算法 美中不足在于只能确定函数是平衡的还是非平衡的,无法确定函数具体的内容,即无法直接解出函数 Bernstein-Vazirani算法ÿ…...
jrebel IDEA 热部署
1 下载 2022.4.1 JRebel and XRebel - IntelliJ IDEs Plugin | Marketplace 2 选择下载好的zip 离线安装IDEA 插件 重启IDEA 3 打开 [Preference -> JRebel & XRebel] 菜单,输入 GUID address 为 https://jrebel.qekang.com/1e67ec1b-122f-4708-87d…...
pdf拆分成各个小pdf的方法
背景:由于某些缘故,一个大的pdf需要拆分成页数少的pdf,或者pdf需要去掉指定页,那么就有必要对pdf进行重新编辑,这里需要用到一个库,直接进行操作即可。 当使用Python时,可以使用PyMuPDF库来拆分PDF文件。以下是一个示例代码, import fitz # PyMuPDF def split_pdf(i…...
IntelliJ IDEA 常用快捷键一览表(通用型,提高编写速度,类结构、查找和查看源码,替换与关闭,调整格式)
文章目录 IntelliJ IDEA 常用快捷键一览表1-IDEA的日常快捷键第1组:通用型第2组:提高编写速度(上)第3组:提高编写速度(下)第4组:类结构、查找和查看源码第5组:查找、替换…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...
解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...
嵌入式常见 CPU 架构
架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集,单周期执行;低功耗、CIP 独立外设;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel(原始…...
土建施工员考试:建筑施工技术重点知识有哪些?
《管理实务》是土建施工员考试中侧重实操应用与管理能力的科目,核心考查施工组织、质量安全、进度成本等现场管理要点。以下是结合考试大纲与高频考点整理的重点内容,附学习方向和应试技巧: 一、施工组织与进度管理 核心目标: 规…...
WebRTC调研
WebRTC是什么,为什么,如何使用 WebRTC有什么优势 WebRTC Architecture Amazon KVS WebRTC 其它厂商WebRTC 海康门禁WebRTC 海康门禁其他界面整理 威视通WebRTC 局域网 Google浏览器 Microsoft Edge 公网 RTSP RTMP NVR ONVIF SIP SRT WebRTC协…...
