[USACO04OPEN] The Cow Lineup
题目描述
约翰的 N ( 1 ≤ N ≤ 100000 ) N ( 1 \leq N \leq 100000 ) N(1≤N≤100000) 只奶牛站成了一列。每只奶牛都写有一个号牌,表示她的品种,号牌上的号码在 1 … K ( 1 ≤ K ≤ 10000 ) 1 \ldots K ( 1 \leq K \leq 10000 ) 1…K(1≤K≤10000)范围内。
比如有这样一个队列:1,5,3,2,5,3,4,4,2,5,1,2,3
根据约翰敏锐的数学神经,他发现一些子序列在这个队列里出现,比如"3,4,1,3",而另一些没有。子序列的各项之间穿插有其他数,也可认为这个子序列存在。现在,他想用 1 ∼ K 1∼K 1∼K 之间的整数构造一个最短的子序列,使之不在奶牛序列里出现。达个子序列的长度是多少
输入格式
第1行输入两个整数 N N N 和 K K K ,接下来 N N N 行输入奶牛序列.
输出格式s
输出一行,最短的不出现子序列的长度。
样例 #1
样例输入 #1
14 5
1
5
3
2
5
1
3
4
4
2
5
1
2
3
样例输出 #1
3
提示
样例解释:
所有长度为 1 1 1 和 2 2 2 的可能的子序列都出现了,但长度为 3 的子序列 “ 2 , 2 , 4 ” “2,2,4” “2,2,4” 却没有出现。
这道题要用到二分(也就是分治)来做这道题,首先我们要知道最短的不出现子序列的长度是什么,也就是找到一个靠后的第一次出现的数,然后,在这个第一次出现为序列的序列继续开始查找,直到发现没有出现的子序列,然后计算数列长度
以下是代码:
#include <bits/stdc++.h>
const int N=10050;
int n,k,x;
int vis[N],tot,ans;
int main(){scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%d",&x);if(!vis[x])vis[x]=1,tot++;if(tot==k){memset(vis,0,sizeof(vis));tot=0;ans++;}}printf("%d\n",ans+1);return 0;
}
相关文章:
[USACO04OPEN] The Cow Lineup
题目描述 约翰的 N ( 1 ≤ N ≤ 100000 ) N ( 1 \leq N \leq 100000 ) N(1≤N≤100000) 只奶牛站成了一列。每只奶牛都写有一个号牌,表示她的品种,号牌上的号码在 1 … K &#x…...
软件工具集合
代码文档自动生成工具: Doxygen download 软件分析工具: perf gdb flamegraph 代码量统计: vscode插件:VS Code Counter 代码备注 vsocde插件: Line Note...
C#利用openvino部署PP-TinyPose人体姿态识别
【官方框架地址】 github.com/PaddlePaddle/PaddleDetection 【算法介绍】 关键点检测算法往往需要部署在轻量化、边缘端设备上,因此长期以来都存在一个难题:精度高、速度则慢、算法体积也随之增加。而PP-TinyPose的出世彻底打破了这个僵局,…...
MindSpore Serving与TGI框架 の 对比
一、MindSpore Serving MindSpore Serving是一款轻量级、高性能的服务工具,帮助用户在生产环境中高效部署在线推理服务。 使用MindSpore完成模型训练>导出MindSpore模型,即可使用MindSpore Serving创建该模型的推理服务。 MindSpore Serving包含以…...
两阶段提交协议三阶段提交协议
两阶段提交协议 分布式事务是指会涉及到操作多个数据库的事务,在分布式系统中,各个节点之间在物理上相互独立,通过网络进行沟通和协调。 XA 就是 X/Open DTP 定义的交易中间件与数据库之间的接口规范(即接口函数),交易…...
6-Docker Compose-tomcat application(指定官方镜像)
1.创建docker-compose.yml文件,添加如下内容并保存 vim docker-compose.yml [root@centos79 ~]# cat docker-compose.yml #yml文件 version: 3 #版本号,默认为3 services:tomcat-ztj: #定…...
宝塔安装的imagemagick不能用,必须自己手动安装
1 安装 用composer安装 2 宝塔安装的imagemagick不能用,必须自己手动安装(3.4.3版本 php 7.3) 1 步骤: wget https://pecl.php.net/get/imagick-3.4.3.tgz tar -zxf imagick-3.4.3.tgz cd imagick-3.4.3 /www/server/php/73…...
解决在test以外的目录下导入junit无效
以上引用来自src目录下的文件,可以看到,和junit有关的导入都飘红,但明明junit已经被正确导入进了项目中。 再看右侧的Maven的依赖下方,junit的右边有一个很不起眼的(test) 这是因为junit作为测试框架,可能包含仅适用于…...
docker 在线安装mysql 8.0.21版本
1、拉取mysql 8.0.21版本镜像 2、查看镜像 docker images 3、在宿主机 /usr/local/mysql 下的 conf 文件夹下,创建 my.cnf 文件,并编辑内容 [mysql] default-character-setutf8 [client] port3306 default-character-setutf8 [mysqld] port3306 se…...
WPF DatePicker与Calendar的使用和样式修改
什么是DatePicker,Calendar Calendar:日历(显示年月日视图控件)DatePicker:日期选择器(是一个更小的控件,点击控件时才会弹出一个日历) Calendar使用 常用属性 DisplayMode&#…...
从0开始python学习-40.通过正则表达式/json进行接口关联
目录 1. 正则表达式:使用re库(需安装-pip install re),只能提取字符串的数据。 1.1 re.seach:提取一个值,得到的是一个对象,通过下标group(1)取值,如果没有匹配到值则返回None 1.…...
【React系列】高阶组件
本文来自#React系列教程:https://mp.weixin.qq.com/mp/appmsgalbum?__bizMzg5MDAzNzkwNA&actiongetalbum&album_id1566025152667107329) 一. 高阶组件 1.1. 认识高阶组件 什么是高阶组件呢?相信很多同学都听说过,也用过 高阶函数&…...
听GPT 讲Rust源代码--src/tools(38)
File: rust/src/tools/clippy/clippy_dev/src/lib.rs rust/src/tools/clippy/clippy_dev/src/lib.rs文件是Clippy开发工具的入口文件,其作用是提供Clippy开发过程中所需的功能和工具。Clippy是一个Rust代码的静态分析工具,用于提供各种有用的代码规范、编…...
.NET C# 如何获取object对象的数据
如何获取object对象的数据 在DAL层,一般会封装一些返回值,返回的类型就会为object ,但是需要其中的值进行判断 public static object SaveFileIns(string filepath){return new { path pathlist, file_name fileNamelist, Message "…...
使用IDEA创建使用 JDK8 的 2.x.x 版本的 Spring Boot 项目以及 Spring Boot 项目如何修改JDK版本
目录 一、在阿里云上官网上创建项目 二、将 IDEA 中创建项目的源地址修改为阿里云官网 三、创建 3.x.x 的项目之后修改配置降低至 2.7.x 版本和使用 JDK8(修改 Spring Boot 的 JDK 版本同理) 从上面的 Spring Boot 官网的截图中可以发现,自…...
游戏服务器整体架构思考
1.启动层 不管是单体架构还是微服务架构,其实服务器本身都是要启动的。 不管是用grpc实现远程调用,还是dubbo,还是说就一个简单的tcp监听,都是要启动的。 启动的时候,肯定要整合下controller接入层,不管是叫…...
labelme 标注的数据集转化为Mask-Rcnn适用的数据集
labelme 标注的数据集转化为Mask-Rcnn适用的数据集 食用步骤 1.labelme标注数据时,将生成的json文件和原图保存在一起 2.只需提供labelme生成的数据的文件夹,和maskrcnn的数据集文件夹,运行代码就会自动进行处理 3.代码会在提供的maskrcn…...
x-cmd pkg | tig - git 文本模式界面
目录 简介首次用户功能特点类似工具与竞品进一步探索 简介 tig 由 Jonas Fonseca 于 2006 年使用 C 语言创建的 git 交互式文本命令行工具。旨在开启交互模式快速浏览 git 存储库的信息以及 git 命令的运行。 首次用户 使用 x tig 即可自动下载并使用 在终端运行 eval "…...
信息论与编码期末复习——概念论述简答题(一)
个人名片: 🦁作者简介:一名喜欢分享和记录学习的在校大学生 🐯个人主页:妄北y 🐧个人QQ:2061314755 🐻个人邮箱:2061314755qq.com 🦉个人WeChat:V…...
[Kubernetes]4. 借助腾讯云TKE快速创建Pod、Deployment、Service部署k8s项目
前面讲解了通过命令行方式来部署k8s项目,下面来讲讲通过腾讯云TKE来快速创建Pod、Deployment、Service部署k8s项目,云平台搭建Kubernetes可参考[Kubernetes]1.Kubernetes(K8S)介绍,基于腾讯云的K8S环境搭建集群以及裸机搭建K8S集群 一.通过腾讯云TKE创建集群 1.创建集群 参考上…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
