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

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&#xff0c;你可以对S执行操作&#xff0c;选择两个字符&#xff0c;将前面的改为A&#xff0c;后面的改为B&#xff0c;最少操作几次可以把S改成T。如果改不成就输出-1。 从左往右一个一个改过去&#xff0c;分类讨论&#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…...

【软件测试】学习笔记-网站可扩展性架构设计

可扩展性&#xff0c;指的是网站的架构设计能够快速适应需求的变化&#xff0c;当需要增加新的功能实现时&#xff0c;对原有架构不需要做修改或者做很少的修改就能够快速实现新的业务需求。 从这个定义中&#xff0c;我们很容易就可以得出衡量网站可扩展性设计优秀与否的主要标…...

深度学习常用代码总结(k-means, NMS)

目录 一、k-means 算法 二、NMS 一、k-means 算法 k-means 是一种无监督聚类算法&#xff0c;常用的聚类算法还有 DBSCAN。k-means 由于其原理简单&#xff0c;可解释强&#xff0c;实现方便&#xff0c;收敛速度快&#xff0c;在数据挖掘、数据分析、异常检测、模式识别、金…...

数据结构·顺序表应用

本节应用是要用顺序表实现一个通讯录&#xff0c;收录联系人的姓名、性别、电话号码、住址、年龄 ​​​​​​​ 顺序表的实现在上一节中已经完成了&#xff0c;本节的任务其实就是应用上节写出来的代码的那些接口函数功能&#xff0c;做出来一个好看的&#xff0c;可…...

第一个 OpenGL 程序:旋转的立方体(VS2022 / MFC)

文章目录 OpenGL API开发环境在 MFC 中使用 OpenGL初始化 OpenGL绘制图形重置视口大小 创建 MFC 对话框项目添加 OpenGL 头文件和库文件初始化 OpenGL画一个正方形OpenGL 坐标系改变默认颜色 重置视口大小绘制立方体使用箭头按键旋转立方体深度测试添加纹理应用纹理换一个纹理 …...

剩余银饰的重量 - 华为OD统一考试

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C 题目描述 有N块二手市场收集的银饰&#xff0c;每块银饰的重量都是正整数&#xff0c;收集到的银饰会被熔化用于打造新的饰品。 每一回合&#xff0c;从中选出三块 最重的…...

redis远程连接不上解决办法

问题描述&#xff1a; redis远程服务端运行在192.168.3.90计算机上&#xff0c;客户端计算机&#xff08;ip:192.168.3.110&#xff09;通过redsi-cli.exe客户端工具连接时&#xff0c;没有反应&#xff0c;连接不上。 如图所示&#xff1a; 解决步骤&#xff1a; 步骤一&…...

利用Anaconda安装pytorch和paddle深度学习环境+pycharm安装后不能调用pytorch和paddlepaddle框架

问题现象&#xff1a; 之前安装后不能在添加pytorch和paddlepaddle框架 原因&#xff08;疑似&#xff09;&#xff1a; 在终端中显示pytorch和paddle在C盘但是安装是安装在J盘 解决办法&#xff1a; 卸载、删除文件重新安装后可以看到文件位置在J盘中 但是选择时还是显示C…...

Eclipses安装教程

一、下载开发工具包 1、开发工具包JDK 下载地址链接&#xff1a;https://www.oracle.com/cn/java/technologies/downloads/ 下载教程&#xff1a; 1&#xff09;点击链接&#xff0c;可以跳转到页面 2&#xff09;下滑页面&#xff0c;找到开发工具包 3&#xff09; 记住下载之…...

安装python版opencv的一些问题

安装python版opencv的一些问题 OpenCV是知名的开源计算机视觉算法库&#xff0c;提供了C\Python\Java版共享库。 在Python中使用OpenCV格外简单&#xff0c;一句命令就能安装&#xff0c;一行import就能引入&#xff0c;可谓是神器。然而&#xff0c;在实际使用中可能遇到一些…...

RabbitMQ入门实战

RabbitMQ 是一个开源的消息中间件&#xff0c;实现了高级消息队列协议&#xff08;AMQP&#xff09;&#xff0c;用于在分布式系统中进行消息传递。它能够在应用之间传递消息&#xff0c;解耦应用组件&#xff0c;提高系统的可伸缩性和可维护性。RabbitMQ 使用高级消息队列协议…...

vue3-模版引用ref

1. 介绍 概念&#xff1a;通过 ref标识 获取真实的 dom对象或者组件实例对象 2. 基本使用 实现步骤&#xff1a; 调用ref函数生成一个ref对象 通过ref标识绑定ref对象到标签 代码如下&#xff1a; 父组件&#xff1a; <script setup> import { onMounted, ref } …...

C# 十大排序算法

以下是常见的十大排序算法&#xff08;按照学习和实现的顺序排列&#xff09;&#xff1a; 冒泡排序&#xff08;Bubble Sort&#xff09;选择排序&#xff08;Selection Sort&#xff09;插入排序&#xff08;Insertion Sort&#xff09;希尔排序&#xff08;Shell Sort&…...

面试之Glide如何绑定Activity的生命周期

Glide绑定Activity生命周期 Glide.with() 下面都是它的重载方法&#xff0c;Context&#xff0c;Activity&#xff0c;FragmentActivity, Fragment, android.app.Fragment fragment,View都可以作为他的参数&#xff0c;内容大同小异&#xff0c;都是先getRetriever&#xff0…...

从 fatal 错误到 sync.Map:Go中 Map 的并发策略

为什么 Go 语言在多个 goroutine 同时访问和修改同一个 map 时&#xff0c;会报出 fatal 错误而不是 panic&#xff1f;我们该如何应对 map 的数据竞争问题呢&#xff1f; 这篇文章将带你一步步了解背后的原理&#xff0c;并引出解决 map 并发问题的方案。 Map 数据竞争 首先…...

Simon算法详解

0.0 Intro 相关的算法&#xff1a; Deutsh-Jozsa算法&#xff1a; 第一个量子算法对经典算法取得指数级加速的算法 美中不足在于只能确定函数是平衡的还是非平衡的&#xff0c;无法确定函数具体的内容&#xff0c;即无法直接解出函数 Bernstein-Vazirani算法&#xff…...

jrebel IDEA 热部署

1 下载 2022.4.1 JRebel and XRebel - IntelliJ IDEs Plugin | Marketplace 2 选择下载好的zip 离线安装IDEA 插件 重启IDEA 3 打开 [Preference -> JRebel & XRebel] 菜单&#xff0c;输入 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组&#xff1a;通用型第2组&#xff1a;提高编写速度&#xff08;上&#xff09;第3组&#xff1a;提高编写速度&#xff08;下&#xff09;第4组&#xff1a;类结构、查找和查看源码第5组&#xff1a;查找、替换…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...