当前位置: 首页 > 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;也是在开发过程中使用的最多…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...