当前位置: 首页 > 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;查找、替换…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...