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组:查找、替换…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
Modbus RTU与Modbus TCP详解指南
目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...
