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

【蓝桥集训】第五天——递推

作者:指针不指南吗
专栏:Acwing 蓝桥集训每日一题

🐾或许会很慢,但是不可以停下来🐾

文章目录

  • 1.砖块

递推算法是一种简单的算法,通过已知条件,利用特定关系得出中间推论,逐步递推,直到得到结果为止

1.砖块

n 个砖块排成一排,从左到右编号依次为 1∼n。

每个砖块要么是黑色的,要么是白色的。

现在你可以进行以下操作若干次(可以是 00 次):

选择两个相邻的砖块,反转它们的颜色。(黑变白,白变黑)

你的目标是通过不超过 3n 次操作,将所有砖块的颜色变得一致。

输入格式

第一行包含整数 T,表示共有 T 组测试数据。

每组数据第一行包含一个整数 n。

第二行包含一个长度为 n 的字符串 s。其中的每个字符都是 WB,如果第 i 个字符是 W,则表示第 i 号砖块是白色的,如果第 i 个字符是 B,则表示第 i 个砖块是黑色的。

输出格式

每组数据,如果无解则输出一行 −1。

否则,首先输出一行 k,表示需要的操作次数。

如果 k>0,则还需再输出一行 k 个整数,p1,p2,…,pk。其中 pi 表示第 i 次操作,选中的砖块为 pi 和 pi+1 号砖块。

如果方案不唯一,则输出任意合理方案即可。

数据范围

1≤T≤10,
2≤n≤200。

输入范围:

4
8
BWWWWWWB
4
BWBB
5
WWWWW
3
BWB

输出样例:

3
6 2 4
-1
0
2
2 1
  • 思路

    • 最后的结果可以分成两种情况:全白或者是全黑;

    • 我们操作的位置只有 n-1 种,所以不用考虑 3n 的情况;

    • 每个位置反转两次,相当于没有反转,所以我们只要考虑每个位置要不要操作就可以(0或者1);

    • 如果 i 位置和我们想要的颜色不同,则操作,否则,不,所以说每个位置的操作都是确定的;

    把每一个位置递推一下,到最后一个

    • 最后一个在前一个位置操作或者是没有操作过后,不能操作:判断一下,如果与第一个相同,则说明符合题意。
  • 代码实现

    #include<bits/stdc++.h>
    using namespace std;int n;void update(char &a)
    {if(a=='W') a='B';else a='W';
    }bool check(string s,char x)
    {vector<int> ans; //数组 ans 存操作的位置 for(int i=0;i+1<n;i++){  if(s[i]!=x){  //如果不是我们想要的,则更新update(s[i]);update(s[i+1]);ans.push_back(i);  //把操作位置放入数组中}}if(s.back()!=s[0]) return false;  //最后一个无法改变,如果与前面不同,则不能实现cout<<ans.size()<<endl;for(auto i:ans) cout<<i+1<<' ';  //输出结果return true;
    }int main()
    {int T;cin>>T;while(T--){string s;cin>>n>>s;if(!check(s,'W')&&!check(s,'B')) puts("-1");  //如果全白或者是全黑都不可以,则输出 -1;} return 0;} 
    

Alt

相关文章:

【蓝桥集训】第五天——递推

作者&#xff1a;指针不指南吗 专栏&#xff1a;Acwing 蓝桥集训每日一题 &#x1f43e;或许会很慢&#xff0c;但是不可以停下来&#x1f43e; 文章目录1.砖块递推算法是一种简单的算法&#xff0c;通过已知条件&#xff0c;利用特定关系得出中间推论&#xff0c;逐步递推&…...

qnx的网络知识记录

1、网络驱动加载http://www.qnx.com/developers/docs/7.1/index.html#com.qnx.doc.core_networking/topic/drivers_Loading.html使用mount挂载io-pkt模块mount -Tio-pkt /lib/dll/devnp-e1000.sonicinfo 命令可以查看网卡的各种状态&#xff0c;包括phy的状态2、iopktiopkt的介…...

【Vue/基础知识】Vue基础知识(一)

如果觉得我的分享有一定帮助&#xff0c;欢迎关注我的微信公众号 “码农的科研笔记”&#xff0c;了解更多我的算法和代码学习总结记录。或者点击链接扫码关注 【Vue/基础知识】Vue基础知识&#xff08;一&#xff09; 1、v-show 和 v-if 指令的共同点和不同点&#xff1f; 共…...

Iceberg实战踩坑指南

第 1 章 介绍 Apache Iceberg 是一种用于大型分析数据集的开放表格&#xff0c;Iceberge 向 Trino 和 Spark 添加了使用高性能格式的表&#xff0c;就像 Sql 表一样。 Iceberg 为了避免出现不变要的一些意外&#xff0c;表结构和组织并不会实际删除&#xff0c;用户也不需要特…...

预告|2月25日 第四届OpenI/O 启智开发者大会昇腾人工智能应用专场邀您共启数字未来!

如今&#xff0c;人工智能早已脱离科幻小说中的虚构想象&#xff0c;成为可触及的现实&#xff0c;并渗透到我们的生活。随着人工智能的发展&#xff0c;我们正在迎来一个全新的时代——数智化时代。数据、信息和知识是这个时代的核心资源&#xff0c;而人工智能则是这些资源的…...

UnRaid虚拟机安装OpenWrt软路由

文章目录0、前言1、Openwrt虚拟机安装1.1、前提&#xff0c;需要先在UnRaid中开启虚拟机&#xff1a;1.2、下载OpenWrt虚拟机镜像并上传至UnRaid共享文件夹1.3、创建OpenWrt虚拟机2、开启并设置OpenWrt虚拟机2.1、修改OpenWrt管理ip2.2、OpenWrt的上网设置0、前言 最近折腾了很…...

开发日记-lombok

开发日记-lombok环境问题解决方案&#xff1a;1 Data注解失效 无法正常生成 get和set方法2 RequiredArgsConstructor(onConstructor _(Lazy)) 符号_无法识别环境 idea2020.1lombok1.18.24jdk1.8 问题 Data注解失效 无法正常生成 get和set方法RequiredArgsConstructor(onCons…...

Web3中文|2023年zk赛道爆发,即将推出的Polygon zkEVM有多重要?

2月15日&#xff0c;以太坊第2层解决方案提供商Polygon终于公布了备受期待的扩展更新&#xff0c;其零知识以太坊虚拟机&#xff08;zkEVM&#xff09;主网的测试版定于3月27日发布。 据官方消息报道&#xff0c;自去年10月上线测试网以来&#xff0c;已取得许多重要的里程碑&…...

【自然语言处理】主题建模:Top2Vec(理论篇)

主题建模&#xff1a;Top2Vec&#xff08;理论篇&#xff09;Top2Vec 是一种用于 主题建模 和 语义搜索 的算法。它自动检测文本中出现的主题&#xff0c;并生成联合嵌入的主题、文档和词向量。 算法基于的假设&#xff1a;许多语义相似的文档都可以由一个潜在的主题表示。首先…...

【ICLR 2022】重新思考点云中的网络设计和局部几何:一个简单的残差MLP框架

文章目录RETHINKING NETWORK DESIGN AND LOCAL GEOMETRY IN POINT CLOUD: A SIMPLE RESIDUAL MLP FRAMEWORKPointMLP残差点模块几何仿射模块精简版模型&#xff1a;PointMLP-elite实验结果消融实验RETHINKING NETWORK DESIGN AND LOCAL GEOMETRY IN POINT CLOUD: A SIMPLE RESI…...

《MySQL学习》 count(*) 原理

一 . count&#xff08;*&#xff09;的实现方式 MyISAM 引擎把一个表的总行数存在了磁盘上&#xff0c;因此执行 count() 的时候会直接返回这个数&#xff0c;效率很高&#xff1b; 而 InnoDB 引擎就麻烦了&#xff0c;它执行 count(*) 的时候&#xff0c;需要把数据一行一行…...

时间序列数据预测的类型

本文主要内容是使用LSTM网络进行不同类型的时间序列预测任务&#xff0c;不涉及代码&#xff0c;仅仅就不同类型的预测任务和数据划分进行说明。 参考文章&#xff1a;https://machinelearningmastery.com/how-to-develop-lstm-models-for-time-series-forecasting/ 注&#xf…...

sk_buff结构体成员变量说明

一. 前言 Socket Buffer的数据包在穿越内核空间的TCP/IP协议栈过程中&#xff0c;数据内容不会被修改&#xff0c;只是数据包缓冲区中的协议头信息发生变化。大量操作都是围绕sk_buff结构体来进行的。 sk_buff结构的成员大致分为3类&#xff1a;结构管理域&#xff0c;常规数据…...

springbatch设置throttle-limit参数不生效

背景描述 当springbatch任务处理缓慢时&#xff0c;就需要使用多线程并行处理任务。 参数throttle-limit用于控制当前任务能够使用的线程数的最大值。 调整throttle-limit为10时&#xff0c;处理线程只有8&#xff0c;再次增大throttle-limit值为20&#xff0c;处理线程依旧为…...

用 tensorflow.js 做了一个动漫分类的功能(一)

前言&#xff1a;浏览某乎网站时发现了一个分享各种图片的博主&#xff0c;于是我顺手就保存了一些。但是一张一张的保存实在太麻烦了&#xff0c;于是我就想要某虫的手段来处理。这样保存的确是很快&#xff0c;但是他不识图片内容&#xff0c;最近又看了 mobileNet 的预训练模…...

看完这篇Vue-element-admin,跟面试官聊骚没问题

Vue-element-admin vue-element-admin 是一个后台前端解决方案&#xff0c;它基于 vue 和 element-ui实现。它使用了最新的前端技术栈&#xff0c;内置了 i18 国际化解决方案&#xff0c;动态路由&#xff0c;权限验证&#xff0c;提炼了典型的业务模型&#xff0c;提供了丰富…...

2022年全国职业院校技能大赛(中职组)网络安全竞赛试题A(5)

目录 模块A 基础设施设置与安全加固 一、项目和任务描述&#xff1a; 二、服务器环境说明 三、具体任务&#xff08;每个任务得分以电子答题卡为准&#xff09; A-1任务一 登录安全加固&#xff08;Windows&#xff09; 1.密码策略 a.密码策略必须同时满足大小写字母、数…...

基于Java+SpringBoot+Vue+Uniapp前后端分离商城系统设计与实现

博主介绍&#xff1a;✌全网粉丝3W&#xff0c;全栈开发工程师&#xff0c;从事多年软件开发&#xff0c;在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战✌ 博主作品&#xff1a;《微服务实战》专栏是本人的实战经验总结&#xff0c;《Spring家族及…...

新建ES别名 添加别名 切换别名

# 查询别名指向到哪个索引 GET bebd_factory_search/_alias # 查询这个索引使用了什么别名 GET bebd_factory_search_1588250935622/_alias # 删除索引 DELETE bebd_factory_search_1588250935622 # 新建别名 POST /_aliases { "actions": [ { "ad…...

MySQL —— 内外连接

目录 表的内外连接 一、内连接 二、外连接 1. 左外连接 2. 右外连接 表的内外连接 表的连接分为内连和外连 一、内连接 内连接实际上就是利用where子句对两种表形成的笛卡儿积进行筛选&#xff0c;我们前面博客中的查询都是内连接&#xff0c;也是在开发过程中使用的最多…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...

ui框架-文件列表展示

ui框架-文件列表展示 介绍 UI框架的文件列表展示组件&#xff0c;可以展示文件夹&#xff0c;支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项&#xff0c;适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...