【2022-09-14】米哈游秋招笔试三道编程题
第一题:最短子串
题目描述
米小游拿到了一个字符串,她想截取一个连续子串,使得该子串中包含至少k个连续的“mihoyo”。
你可以帮米小游求出最短的子串长度,以及对应的子串位置吗?
输入描述
第一行输入两个正整数n和k,用空格隔开。
第二行输入一个长度为n的、仅由小写字母组成的字符串。1≤k≤n≤200000
22 2
mihoyoyomihoyomimihoyo
输出描述
如果不存在这样一个连续子串,请输出-1。
否则输出两个正整数l,r,代表选取的子串的左下标和右下标(整个字符串左下标为0,右下标为n-1)。
请务必保证选择的连续子串包含至少k个"mihoyo",且长度是最短的。有多解时输出任意即可。
0 13
代码与测试
#include<iostream>
#include<string>
#include<vector>
#define NMAX 200000
using namespace std;
int n, k;
string S;
vector<pair<int, int>> res;
string standard = "mihoyo";
int main() {cin >> n >> k >> S;int p1 = 0, p2 = 0, pre = 0;for (; p1 < n; p1++) {if (S[p1] == standard[p2]) {if (!p2) pre = p1;//若为第一个,记录下来p2++;if (p2 == 6) { //若为最后一个,则直接添加到Res中res.push_back(make_pair(pre, p1));p2 = 0;}}else p2 = 0;//不相等直接略过}/*for (int i = 0; i < res.size(); i++) {cout << res[i].first << " " << res[i].second << endl;}*/int size = NMAX;pair<int, int> ret;for (int i = 0; i < res.size(); i++) {if (i + k > res.size()) break;if (res[i + k -1].second - res[i].first < size) {size = res[i + k -1 ].second - res[i].first;ret.first = res[i].first;ret.second = res[i + k -1].second;}}if (size == NMAX) cout << -1 << endl;else cout << ret.first << " " << ret.second << endl;
}
测试用例:
In:
53 2
hsuimihoyomsmihoyoshdusicmihoyomihoyomimimishudmihoyo
Out:
25 36In:
65 3
hsuimihoyomsmihoyomihoyomihoyoshdusicmihoyomihoyomimimishudmihoyo
Out:
12 29
第二题:猜数字
题目描述
米小游心中想了一个正整数,她邀请了n个人来猜这个数。每个人会猜一个数ai,然后米小游会告诉对方猜的结果:大于等于米小游想的数(≥)或者小于米小游想的数(<)。
猜谜结束后,米小游统计了共有x个≥和y个<。请你判断米小游初始想的数有多少种不同的可能?
输入描述
第一行输入一个正整数n,代表猜谜的人数。
第二行输入n个正整数ai,代表每个人猜的数字。
第三行输入两个整数x和y,用空格隔开。
1≤x+y=n≤1e5,1 ≤ ai ≤ 1e9
3
1 5 3
0 3
输出描述
如果有无穷多种可能,输出"infinity"
否则输出一个整数,代表米小游心中想的数的不同可能数量。
infinity
代码与测试
#include<iostream>
#include<algorithm>
using namespace std;
#define NMAX 100005
int n, x, y;
int num[NMAX];
int main() {cin >> n;for (int i = 0; i < n; i++) cin >> num[i];cin >> x >> y;sort(num, num+n);if (x == n) cout << num[0];else if (y == n) cout << "infinity";else cout << num[y] - num[y - 1];
}
In:
3
1 5 3
0 3
Out:
infinityIn:
9
12 32 21 902 12 90 129 12 90
4 5Out:
58In:
9
12 32 21 902 12 90 129 12 90
9 0
Out:
12
C++中的sort
第三题:树的连通块
题目描述
米小游有一棵有根树,树上共有n个节点。
米小游指定了一个节点x为根,然后定义所有相邻的、编号奇偶性相同的节点为一个连通块。
米小游想知道,所有子树(共有n个子树)的连通块数量之和是多少?
举个例子:
如上图,3号节点被指定为根
然后3-1-5作为一个连通块,4号节点和2号节点为单独的连通块。
那么1号节点到5号节点,每个节点的子树连通块数量分别为:2、1、3、1、1,总连通块数量是8。
输入描述
5 3
1 2
1 3
3 4
5 1
输出描述
8
代码与测试
#include<iostream>
#include<vector>
using namespace std;
int n, root;
#define NMAX 100005
int res = 0;
struct node{int s = 1;vector<int> adj;
}T[NMAX];
void dfs(int r, int fa) {int leaf = 1;for (int i = 0; i < T[r].adj.size(); i++) {int son = T[r].adj[i];if (son == fa) continue;else {leaf = 0;dfs(son, r);if (son % 2 == r % 2) T[r].s += (T[son].s - 1);else T[r].s += T[son].s;}}if (leaf) T[r].s = 1;res += T[r].s;
}
int main() {int x, y;cin >> n >> root;for (int i = 0; i < n - 1; i++) {cin >> x >> y;T[x].adj.push_back(y);T[y].adj.push_back(x);}dfs(root,0);cout << res;
}
In:
5 2
1 2
1 3
3 4
5 1
Out:
9In:
5 3
1 2
1 3
3 4
5 1
Out:
8
原题链接
相关文章:

【2022-09-14】米哈游秋招笔试三道编程题
第一题:最短子串 题目描述 米小游拿到了一个字符串,她想截取一个连续子串,使得该子串中包含至少k个连续的“mihoyo”。 你可以帮米小游求出最短的子串长度,以及对应的子串位置吗? 输入描述 第一行输入两个正整数n…...

云监控能力介绍
传统监控介绍 监控系统必要性 监控系统的能力清单 市面上常见商业及开源监控工具集 传统监控体系的不足 云监控介绍 云监控(CloudMonitor)是一项针对云资源和互联网应用进行监控的服务。 云监控为云上用户提供开箱即用的企业级开放型一站式监控解决方…...

HTML 文档类型
<!DOCTYPE> 声明帮助浏览器正确地显示网页。 <!DOCTYPE> 声明 Web 世界中存在许多不同的文档。只有了解文档的类型,浏览器才能正确地显示文档。 HTML 也有多个不同的版本,只有完全明白页面中使用的确切 HTML 版本,浏览器才能完…...

【UML】软件设计说明书 (完结)
目录一. 🦁 前言1.1 编写目的1.2 背景1.3 定义1.4 参考资料二. 🦁 总体设计2.1需求规定2.1.1 系统描述2.1.2 系统用例图2.2 运行环境2.2.1 设备2.2.2 支持软件2.2.3 接口2.2.4 控制2.3 基本设计概念2.4 系统结构三. 🦁 用例分析与设计3.1 用户…...

MATLAB——FFT(快速傅里叶变换)
基础知识 FFT即快速傅里叶变换,利用周期性和可约性,减少了DFT的运算量。常见的有按时间抽取的基2算法(DIT-FFT)按频率抽取的基2算法(DIF-FFT)。 1.利用自带函数fft进行快速傅里叶变换 若已知序列x[4,3,2,6…...

力扣-进店却未进行过交易的顾客
大家好,我是空空star,本篇带大家了解一道简单的力扣sql练习题。 文章目录前言一、题目:1581. 进店却未进行过交易的顾客二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.正确示范④提交SQL运行…...

一文解决vscode中借助CMake配置使用Opencv过程中的所有问题
vscode中借助CMake配置使用opencv过程中的问题 vscode编译工程的完整过程 编写好CMakeLists.txtvscode中 ctrlshiftp 选择cmake configurevscode中 ctrlshiftp 选择cmake build CMake问题 1. set OpenCV_FOUND to FALSE so package “OpenCV” is considered to be NOT FOU…...

Golang每日一练(leetDay0004)
10. 正则表达式匹配 Regular Expression Matching 给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 . 和 * 的正则表达式匹配。 . 匹配任意单个字符* 匹配零个或多个前面的那一个元素 所谓匹配,是要涵盖 整个 字符串 s的,而不是部分…...

手机忘记密码解锁的 6 大软件方法
您可能想要解锁手机的原因有很多。也许您正在海外旅行并想使用当地的 SIM 卡,或者您可能刚买了一部二手手机并且需要删除之前所有者的个人数据。您可能想知道如何获得可以免费解锁任何手机的软件。Android 用户可以使用他们的指纹、面部识别或 PIN。您也可以通过快速…...

MySQL数据库的基础语法总结(1)
MySql一.数据库,数据表的基本操作1.数据库的基本操作2. 数据表的基本操作2.1 数据库的数据类型2.1.1 整数类型2.1.2 浮点数类型和定点数类型2.1.3 字符串类型2.1.4 日期与时间类型2.2 数据表的基本操作2.2.1 创建一个数据表2.2.2 查看数据表2.2.3 查看表的基本信息的MySQL指令2…...

Linux之进程创建
本节目录1.fork函数初识2.fork函数返回值3.写时拷贝1.fork函数初识 在Linux中,fork函数是一个非常重要的函数,它从已存在的进程中创建一个新进程。新进程叫做子进程,而原进程叫做父进程。 #include <unistd.h> pid_t fork(void); 返回…...

DCL 管理用户与权限控制
目录 DCL 查询用户 案例 权限控制 案例 DCL DCL英文全称是Data Control Language(数据控制语言),用来管理数据库用户、控制数据库的访问权限。 查询用户 1、查询用户 select * from mysql.user; 2、创建用户 CREATE USER 用户名主机名 IDENTIFIED BY 密码;…...

如何使用 Python 检测和识别车牌(附 Python 代码)
文章目录创建Python环境如何在您的计算机上安装Tesseract OCR?技术提升磨砺您的Python技能车牌检测与识别技术用途广泛,可以用于道路系统、无票停车场、车辆门禁等。这项技术结合了计算机视觉和人工智能。 本文将使用Python创建一个车牌检测和识别程序。…...

[Python题解] CodeForces 1804 D. Accommodation
✅作者简介:人工智能专业本科在读,喜欢计算机与编程,写博客记录自己的学习历程。 🍎个人主页:小嗷犬的个人主页 🍊个人网站:小嗷犬的技术小站 🥭个人信条:为天地立心&…...

【设计模式】访问者模式
访问者模式 访问者模式被称为是最复杂的设计模式,比较难理解并且使用频率不高。 在 GoF 的《设计模式》⼀书中,访问者者模式(Visitor Design Pattern)是这么定义的: Allows for one or more operation to be applied to a set o…...

蓝桥杯刷题冲刺 | 倒计时27天
作者:指针不指南吗 专栏:蓝桥杯倒计时冲刺 🐾马上就要蓝桥杯了,最后的这几天尤为重要,不可懈怠哦🐾 文章目录1.递增序列2.等差素数列3.七段码4.亲戚5.连通块中点的数量1.递增序列 题目 链接:&am…...
RV1126_python人脸识别Retinaface+MobilefaceNet
RV1126_python人脸识别Retinaface+MobilefaceNet RV1126 具备RKNN 模块支持大部分如Pytorch、MXNet、Caffe、tensorflow、keras、onnx等常见框架,而且量化部署使用RKNN-toolkit非常方便。以下介绍通过RV1126实现的人脸识别过程。 首先人脸识别需要先做人脸检测>>人脸校正…...

HBase---HBase基础语法
HBase基础语法 文章目录HBase基础语法基本操作进入 HBase 客户端命令行查看命名空间查看命名空间下的表创建命名空间创建表查看表描述禁用/启用删除表新增列族删除列族更改列族存储版本的限制put 增加数据get 查看数据get条件查询删除指定列族下的指定列删除指定行全表扫描全表…...

2023年,PMP有多少含金量呢?
其实围绕以PMP含金量为中心的这个类似的小问题我好像也已经写了不少文章了。首先我肯定PMP的含金量,不管有多少质疑,这的确是事实。因为就是看中了他的价值考的,并且在项目的执行上收获了很多。 具体的可以看我接下来谈的PMP的价值&#x…...
vue动态路由
import Vue from vue import Router from vue-router import layout from ../components/layout Vue.use(Router) // 动态路由 export const asyncRouterMap = [ { path: /home, component: layout, name: home, meta: { title: 首页, icon: el-ic…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...

使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...

C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...

网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...

Unity UGUI Button事件流程
场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

Ubuntu Cursor升级成v1.0
0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开,快捷键也不好用,当看到 Cursor 升级后,还是蛮高兴的 1. 下载 Cursor 下载地址:https://www.cursor.com/cn/downloads 点击下载 Linux (x64) ,…...