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

cf1348B phoenix and beauty(双指针滑动窗口的构造)

C

题面

Problem - 1348B - Codeforces
输出标准输出
凤凰网喜欢美丽的数组。如果一个数组中所有长度为k的子数组
的子数都有相同的总和,那么这个数组就是美丽的。一个数组的子数组是任何连续元素的序列。

凤凰网目前有一个数组a
的长度为n
. 他想在他的数组中插入一些整数,可能是零,这样它··就会变得很漂亮。插入的整数必须是在1
和n
包括在内。整数可以插入任何地方(甚至在第一个或最后一个元素之前或之后),而且他并不是要尽量减少插入的整数的数量。

输入
输入由多个测试案例组成。第一行包含一个整数t
(1≤t≤50
)–测试用例的数量。

每个测试用例的第一行包含两个整数n
和k
(1≤k≤n≤100
).

每个测试用例的第二行包含n
空间分隔的整数(1≤ai≤n
)–Phoenix当前拥有的数组。这个数组可能是也可能不是已经很美。

输出
对于每个测试案例,如果不可能创建一个漂亮的数组,则打印-1。否则,打印两行。

第一行应该包含美丽数组的长度m
(n≤m≤104
). 你不需要最小化m
.

第二行应该包含m
空间分隔的整数(1≤bi≤n
)–这是一个美丽的数组,Phoenix将一些可能为零的整数插入他的数组a后可以得到。
. 你可以打印原本不在数组a中的整数
.

如果有多个解决方案,就打印任何一个。可以保证,如果我们能使数组a
美丽,我们总能使它的结果长度不超过104
.

例子
InputCopy
4
4 2
1 2 2 1
4 3
1 2 2 1
3 2
1 2 3
4 4
4 3 4 2
输出拷贝
5
1 2 1 2 1
4
1 2 2 1
-1
7
4 3 2 1 4 3 2
注意
在第一个测试案例中,我们可以通过插入整数1来使数组a
通过在索引3处插入整数1
在索引3处
(在现有的两个2之间)
s). 现在,所有长度为k=2的子数组
都有相同的和 3
. 存在许多其他可能的解决方案,例如:

2,1,2,1,2,1
1,2,1,2,1,2
在第二个测试案例中,数组已经非常漂亮:所有长度为k=3的子数组
都有相同的和 5
.

在第三个测试案例中,我们可以证明,我们不能插入数字来使数组a
美丽。

在第四个测试案例中,数组b
是美丽的,所有长度为k=4的子数组
的所有子数都有相同的和 10
. 也存在着其他的解决方案。

代码

CodeForces - 1348B Phoenix and Beauty(思维+题干细节)_zaiyang遇见的博客-CSDN博客
见代码问号注释

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int f[N],vis[N],c[N];
***
int main()
{int T;cin>>T;while(T--){memset(f,0,sizeof f);memset(vis,0,sizeof vis);memset(c,0,sizeof c);***int n,k,S=0;多组输入初始化cin>>n>>k;数组长,漂亮长for(int i=1;i<=n;i++){cin>>f[i];if(vis[f[i]]==0){vis[f[i]]=1;c[++S]=f[i];}}读入并记录原数组数据和数据是否出现。记录数组数据种类,并存入c***if(S>k){cout<<-1<<endl;种类大于k则不能构造漂亮因为每个k长度的连续序列里的总和相同的话,必定是要每个k区间元素都具有相同的种类与排列}***else{否则:for(int i=S+1;i<=k;i++)c[i]=c[i-1];***for(int i=k+1;i<=9999;i++)需要构造n*k个这样的连续序列。????????????????????????似乎是因为存在一些排列与要构造k排列不同的子区间,而且又不能打乱n的排列,所以假定最坏情况下每次构造只能满足其中一个元素的排列,这样要构造n-k次。c[i]=c[i-k];距离为k+1cout<<9999<<endl;***for(int i=1;i<=9999;i++)cout<<c[i]<<" ";cout<<endl;}不够k的部分,随便补,可以补成一样的数。大于k的部分,变成和k一样的序列只要具有相同的长度为k的排列,就可以满足题意,突然发现可以用双指针滑动窗口来理解这个题因为以k长度的滑动窗口移动时,k少掉了哪个元素,就会新增哪个元素。最后输出。看到k长度没有提取出双指针滑动窗口套路,不太熟练,要再去加深印象}return 0;
}

考验代码

4:30
4:00
4:00

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10;
int vis[N],f[N],c[N];
int  main(){int T;cin >> T;while(T--){memset(vis,0,sizeof vis);int n,k,siz = 0;cin >> n >> k;for(int i = 1;i <= n;i++){cin >> f[i];if(!vis[f[i]]){vis[f[i]] = true;c[++siz] = f[i];}}if(siz > k){cout << -1 << endl;}else{for(int i = siz + 1;i <= k;i++){c[i] = 1;}for(int i = k+1;i <= n *k;i++){c[i] = c[i-k];}cout << n*k << " " ;for(int i = 1;i <= n*k;i++){cout << c[i] << " " ;}cout << endl;}}return 0;
}

套路:双指针滑动窗口的构造。

前提条件:固定长度的连续区间

双指针滑动窗口特殊性在于每次移动会少一个元素,会多一个元素,
要让总和相同,少掉的元素必须等于新增的元素。

所以如果原数组中即将进入滑动窗口的元素不等于少掉的元素时,
就要插入一个与少掉的元素相等的数作为新增的元素。
一直插入直到原数组中每个元素都进入了滑动窗口。

相关文章:

cf1348B phoenix and beauty(双指针滑动窗口的构造)

C 题面 Problem - 1348B - Codeforces 输出标准输出 凤凰网喜欢美丽的数组。如果一个数组中所有长度为k的子数组 的子数都有相同的总和&#xff0c;那么这个数组就是美丽的。一个数组的子数组是任何连续元素的序列。 凤凰网目前有一个数组a 的长度为n . 他想在他的数组中插入…...

一文读懂JAVA的hashCode方法:原理、实现与应用

目录 一、概述二、实现原理和重写规则三、如何重写hashCode方法3.1 Objects.hash()方法3.2 Apache HashCodeBuilder.3.3 Google Guava3.4 自定义哈希算法四、hashcode和equals的联系五、注意事项和建议5.1 注意事项5.2 建议六、总结一、概述 在Java中,每个对象都有一个hashCod…...

RocketMQ部署

一 安装mq 1.下载RocketMQ 本教程使⽤的是RocketMQ4.7.1版本&#xff0c;建议使⽤该版本进⾏之后的demo训练。 运⾏版&#xff1a;https://www.apache.org/dyn/closer.cgi?pathrocketmq/4.7.1/rocketmq-all-4.7.1-bin-release.zip 源码&#xff1a;https://www.apache.org…...

43岁程序员,投了上万份简历都已读不回,只好把年龄改成40岁,这才有了面试机会,拿到了offer!...

40多岁找工作有多难&#xff1f; 一位43岁的程序员讲述了自己找工作的经历&#xff1a; 80年&#xff0c;大专&#xff0c;目前没到43周岁&#xff0c;年前被裁&#xff0c;简历上的年龄是42岁&#xff0c;两个多月投了上万份简历&#xff0c;99.5%是已读未回。后来改变策略把简…...

MySQL分区表相关知识总结

1.创建分区表&#xff1a; create table t(col11 int null, col22 …) engineinnodb partition by hash(col33) partitions 44; create table t(col11 int null, col22 …) engineinnodb partition by range(id) (partition p0 values less than (10), partition p1 values les…...

outlook邮箱pc/mac客户端下载 含最新版

新的 Outlook for Windows or mac 为 Outlook 应用带来了最新功能、智能辅助功能和新的新式简化设计。 你可以根据自己的风格定制它&#xff0c;并使用新的 Outlook for Windows/mac 执行更多操作&#xff01; 览版&#xff0c;与我们一起开始旅程&#xff0c;并帮助我们塑造新…...

缓存雪崩、缓存穿透、缓存击穿分别是什么?如何解决?

缓存中存放的大多都是热点数据&#xff0c;目的就是从缓存中获取数据&#xff0c;而不用直接访问数据库&#xff0c;从而提高查询效率 缓存雪崩 概念 指缓存在同一时间大面积失效&#xff0c;后面的请求直接访问数据库&#xff0c;导致数据库短时间内压力过大而崩溃&#xff…...

VBA实战篇学习笔记02 Err错误处理

文章目录 专题VI 错误处理课时38 常见错误类型错误代码13 :类型不匹配错误代码91: 对象变量或者with变量未设置错误代码1004: 视具体错误类型而变化 课时39 Err错误处理On Error Resume Next :Resume语句:Resume Next语句:未知错误:Exit SubOn Error Goto 0 专题VI 错误处理 课…...

【Git】拉取代码/提交代码

1.从将本地代码放入远程仓库 (如果有分支的情况) [git checkout xx切换分支后 git add . 将本地所有改动文件新增 commit之后 git push(将代码全部提交)] 分支操作 #查看分支 git branch #创建分支 git branch test #切换分支 git checkout test #修改代码 #提交代码git ad…...

产品预览 | 系统仿真与三维专业场仿真融合——MWORKS模型降阶工具箱

1 引言 近二十年来&#xff0c;数字化技术迅猛发展&#xff0c;以美国和中国提出装备数字工程为标志&#xff0c;人类迈入全新的数字化时代。装备数字化需要对装备的运行状态和行为进行准确的模拟和预测&#xff0c;这就需要利用系统仿真技术。系统仿真技术能够综合考虑装备的…...

我们都遇到过的这些ajax代码到底什么意思?

hello&#xff0c;我是小索奇&#xff0c;本篇文章给大家带来ajax中常用的一些代码&#xff0c;为什么写这些呢&#xff1f; 因为小索奇也看黑马、尚硅谷等老师的视频&#xff0c;在学习java的时候经常会介绍ajax&#xff0c;导致很多不了解的伙伴一脸懵然&#xff0c;以防万一…...

TiDB实战篇-TiCDC

目录 简介 原理 使用场景 使用限制 硬件配置 部署 在安装TiDB的时候部署 扩容部署 操作 管理CDC 管理工具 查看状态 创建同步任务 公共参数 CDC任务同步到MySQL实战 同步命令 查看所有的同步任务 同步任务的状态 管理同步任务 查看一个同步信息的具体情况 …...

ElasticSearch第十七讲 ES索引别名的使用

索引别名 ES中可以为索引添加别名,一个别名可以指向到多个索引中,同时在添加别名时可以设置筛选条件,指向一个索引的部分数据,实现在关系数据库汇总的视图功能,这就是ES中别名的强大之处。别名是一个非常实用的功能,为我们使用索引提供了极大的灵活性,许多ES的API都支持…...

第二个机器学习应用:乳腺癌数据集在决策树模型上的挖掘

目录 决策树优化与可视化 1 决策树分类 2 决策树可视化 3 显示树的特征重要性 特征重要性可视化 决策树回归 1 决策树回归 决策树优化与可视化 1 决策树分类 from sklearn.datasets import load_breast_cancer from sklearn.tree import DecisionTreeClassifier from sk…...

前端canvas截图酷游地址的方法!

前情提要 想在在JavaScript中&#xff0c;酷游专员KW9㍠ㄇEㄒ提供用HTML5的Canvas元素来剪取画面并存成SVG或PNG。 程式写法(一) 首先&#xff0c;需要在HTML中创建一个Canvas元素<canvas id"myCanvas"></canvas> 在JavaScript中&#xff0c;使用canv…...

2018年入学,2021年入职

2018年的春天&#xff0c;凌晨紧张地查着考研成绩&#xff0c;运气好&#xff0c;384&#xff0c;远远超出了我的预期“能进复试就行”&#xff0c;秉承着“尽人事&#xff0c;知天命”的格言&#xff0c;坚持复习完&#xff0c;坚持到考试最后一秒。 在考试之前&#xff0c;我…...

python+nodejs+ssm+vue 基于协同过滤的旅游推荐系统

本文首先介绍了旅游推荐的发展背景与发展现状&#xff0c;然后遵循软件常规开发流程&#xff0c;首先针对系统选取适用的语言和开发平台&#xff0c;根据需求分析制定模块并设计数据库结构&#xff0c;再根据系统总体功能模块的设计绘制系统的功能模块图&#xff0c;流程图以及…...

【STL十四】函数对象(function object)_仿函数(functor)——lambda表达式

【STL十四】函数对象&#xff08;function object&#xff09;_仿函数&#xff08;functor&#xff09;——lambda表达式 一、函数对象&#xff08;function object&#xff09;二、函数对象优点三、分类四、头文件五、用户定义函数对象demo六、std::内建函数对象1、 算术运算函…...

如何写出高质量的前端代码

写出高质量的前端代码是每个前端开发人员的追求。在一个复杂的项目中&#xff0c;代码质量对于项目的可维护性、可扩展性和可读性都有很大的影响。本文将介绍一些如何写出高质量前端代码的技巧和最佳实践。 一、注重代码结构和组织 1.1 遵循一致的命名规范 命名规范是编写高…...

YOLOv7如何提高目标检测的速度和精度,基于优化算法提高目标检测速度

目录 一、学习率调度二、权重衰减和正则化三、梯度累积和分布式训练1、梯度累积2、分布式训练 四、自适应梯度裁剪 大家好&#xff0c;我是哪吒。 上一篇介绍了YOLOv7如何提高目标检测的速度和精度&#xff0c;基于模型结构提高目标检测速度&#xff0c;本篇介绍一下基于优化算…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

Python竞赛环境搭建全攻略

Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型&#xff08;算法、数据分析、机器学习等&#xff09;不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...