虹软科技25届校招笔试算法 A卷

目录

  • 1. 第一题
  • 2. 第二题
  • 3. 论述题

⏰ 时间:2024/08/18
🔄 输入输出:ACM格式
⏳ 时长:2h

本试卷分为不定项选择,编程题,必做论述题和选做论述题,这里只展示编程题和必做论述题,一共三道。

注意,虹软的笔试题目表述的不太清晰,并且也没有给出数据范围,这里针对表述做了一些优化。

1. 第一题

已知字符串 S S S 只包含 A , B A,B A,B 两种字符,设 X X X S S S 中所有 A A A 的索引的集合, Y Y Y S S S 中所有 B B B 的索引的集合。若 S S S 满足以下条件,则称 S S S 为有序字符串。

  • X X X Y Y Y 之间存在双射 f f f,满足 ∀ i ∈ X , f ( i ) > i \forall i\in X, f(i)>i iX,f(i)>i

给定有序字符串 S S S,按照下述规则计算 S S S 的分数,设 P , Q P,Q P,Q 分别为有序字符串

  1. A B AB AB 的分数 = 1 =1 =1
  2. P Q PQ PQ 的分数 = = = P P P 的分数 + + + Q Q Q 的分数
  3. A P B APB APB 的分数 = = = 2 ⋅ P 2\cdot P 2P 的分数

输入描述

输入一个仅包含 A , B A,B A,B 的字符串

输出描述

输出一个整数

题解

这道题本来就有些绕,再加上原本的表述不够清晰,所以很容易误解题意,博主这里稍微修改了下表述。

首先来看什么是有序字符串?这里举一个例子。设 S = A A B A A B B B S=AABAABBB S=AABAABBB ,从而 X = { 0 , 1 , 3 , 4 } , Y = { 2 , 5 , 6 , 7 } X=\{0,1,3,4\},\,Y=\{2,5,6,7\} X={0,1,3,4},Y={2,5,6,7}。我们可以找到一个双射

0 → 2 1 → 5 3 → 6 4 → 7 0\to2\\ 1\to 5 \\ 3\to6\\ 4\to 7 02153647

在这个映射下, 2 > 0 , 5 > 1 , 6 > 3 , 7 > 4 2>0,5>1,6>3,7>4 2>0,5>1,6>3,7>4,因此 S S S 是有序的。更通俗地来讲,对于 S S S 中的每一个 A A A,我们都要在 S S S 中找到一个与之配对 B B B,使得 B B B 的索引大于 A A A 的索引,这样的 S S S 才是有序字符串。

由于双射的性质,易知 ∣ X ∣ = ∣ Y ∣ |X|=|Y| X=Y,因此如果 S S S 是有序的,那么它的长度一定是偶数。此外,一定有 S [ 0 ] = A , S [ − 1 ] = B S[0]=A,\,S[-1]=B S[0]=A,S[1]=B,即 S S S 的首字符一定是 A A A,尾字符一定是 B B B,若不然,假设 S [ 0 ] = B S[0]=B S[0]=B,我们无法在 S S S 中找到与它配对的 A A A,使得 A A A 的下标小于它,对于 S [ − 1 ] S[-1] S[1] 同理。设 S S S 的长度为 2 n , n = 1 , 2 , ⋯ 2n,\;n=1,2,\cdots 2n,n=1,2,,易知 n = 1 n=1 n=1 S = A B S=AB S=AB,我们称这样的 S S S基本串(自己瞎起的名hh,方便后面讲)。

现在回到一般情况,设 S S S 的长度为 2 n 2n 2n X = { a 1 , a 2 , ⋯ , a n } , Y = { b 1 , b 2 , ⋯ , b n } X=\{a_1,a_2,\cdots,a_n\},\,Y=\{b_1,b_2,\cdots,b_n\} X={a1,a2,,an},Y={b1,b2,,bn}。假设 X , Y X,Y X,Y 均是从左向右统计出来的,从而 X , Y X,Y X,Y 均是有序数组。容易得出以下结论:

S 是有序字符串 ⇔ ∀ i , a i < b i S 是有序字符串 \Leftrightarrow \forall i,\,a_i<b_i S是有序字符串i,ai<bi

充分性显然,必要性用反证法证明。

从题中所给的信息,可以猜测,以下两个事件为对立事件(博主还没有来得及证明,欢迎大家在评论区补充):

  • S S S 可以拆成两个有序字符串 P , Q P,Q P,Q,即 S = P Q S=PQ S=PQ。且拆法不会影响到 S S S 的分数。
  • S S S 可以拆成 A P B APB APB 的形式,其中 P P P 是有序的。

很明显可以用递归来做,每次判断当前的 S S S 属于以上哪一种情况,然后递归进行求解, A B AB AB 的分数为 1 1 1 可以作为递归终止条件。

S = A A B A A B B B S=AABAABBB S=AABAABBB 为例。显然 S S S 不能拆成两个有序字符串,因此将其表示成 A P B APB APB 的形式,其中 P = A B A A B B P=ABAABB P=ABAABB 是一定是有序字符串。如果将 P P P 拆成 A R B ARB ARB 的形式,由于 R = B A A B R=BAAB R=BAAB 不是有序的,根据之前的猜想, P P P 一定可以拆成两个有序字符串 U , V U,V U,V,且拆法不会影响到最终分数。很明显 U = A B , V = A A B B U=AB,V=AABB U=AB,V=AABB。于是可以计算 S S S 的分数: S = 2 P = 2 ( U + V ) = 2 ( 1 + 2 ) = 6 S=2P=2(U+V)=2(1+2)=6 S=2P=2(U+V)=2(1+2)=6

#include <bits/stdc++.h>using namespace std;bool is_ordered(const string& s, int l, int r) {vector<int> a_indices, b_indices;for (int i = l; i < r + 1; i++) {if (s[i] == 'A') a_indices.push_back(i);else b_indices.push_back(i);}if (a_indices.size() != b_indices.size()) return false;for (int i = 0; i < a_indices.size(); i++) {if (a_indices[i] > b_indices[i]) return false;}return true;
}// 计算有序字符串s在闭区间[l, r]上的分数
int score(const string& s, int l, int r) {// 基本串情形if (r - l == 1 && s.substr(l, 2) == "AB") return 1;// 看一下成否拆成PQ,分成[l, i], [i + 1, r]for (int i = l; i < r; i++) {if (is_ordered(s, l, i) && is_ordered(s, i + 1, r)) {// 拆法不会影响分数,直接返回即可return score(s, l, i) + score(s, i + 1, r);}}// 因为是对立事件,所以直接返回return 2 * score(s, l + 1, r - 1);
}int main() {string s;cin >> s;int ans = score(s, 0, s.size() - 1);cout << ans << endl;return 0;
}

后续证明了猜想会在这里补充,也欢迎广大网友补充。

2. 第二题

有红、绿、蓝三种颜色(分别用R、G、B表示)的小球,其数量分别为 a , b , c a,b,c a,b,c。现在想将这些小球排成一列,但不希望相邻的两个小球出现相同颜色,请问有多少种排列方法?

输入描述

第一行为 a 、 b 、 c a、b、c abc 对应的三个数字,以空格隔开

输出描述

输出为排列方法的总数

题解

本题较为简单,dfs即可,从左到右枚举并记录上一次放的什么颜色。

#include <bits/stdc++.h>using namespace std;int dfs(int a, int b, int c, int last) {if (a == 0 && b == 0 && c == 0) return 1;int ans = 0;if (last != 0 && a > 0) {ans += dfs(a - 1, b, c, 0);  // 选择红色}if (last != 1 && b > 0) {ans += dfs(a, b - 1, c, 1);  // 选择绿色}if (last != 2 && c > 0) {ans += dfs(a, b, c - 1, 2);  // 选择蓝色}return ans;
}int main() {int a, b, c;cin >> a >> b >> c;cout << dfs(a, b, c, -1) << endl;return 0;
}

其中 dfs(a, b, c, last) 表示红球有 a a a 个,绿球有 b b b 个,蓝球有 c c c 个,且上一次放置的是 last 颜色的情况下,能够放置的方法总数。初始时没有放置,故 last == -1

考虑边界条件。例如只有一个红球的情况下,此时放置方案只有一种,因此

1 = d f s ( 1 , 0 , 0 , − 1 ) = d f s ( 0 , 0 , 0 , 0 ) 1=dfs(1,0,0,-1)=dfs(0,0,0,0) 1=dfs(1,0,0,1)=dfs(0,0,0,0)

故可知边界条件 d f s ( 0 , 0 , 0 , l a s t ) = 1 dfs(0,0,0,last)=1 dfs(0,0,0,last)=1

3. 论述题

假设有一张宽为 M M M,高为 N N N 的黑白图像,每个元素都是 0 0 0 1 1 1,其中 0 0 0 表示黑色像素, 1 1 1 表示白色像素,要在该图像中找到一个宽为 W W W,高为 H H H 的矩形子区域( W < M , H < N W<M,H<N W<M,H<N 且已知),使得该区域内的白色像素数最多,并计算该区域内的白色像素数。
注意 O ( M N H W ) O(MNHW) O(MNHW) 的实现不计分,请用文字描述或者伪代码说明算法过程,并分析时间复杂度。

题解

容易知道枚举所有子矩形的时间复杂度为 O ( ( M − W + 1 ) ⋅ ( N − H + 1 ) ) O((M-W+1)\cdot(N-H+1)) O((MW+1)(NH+1))

计算子矩形中的白色像素数等价于计算子矩形中的所有元素和。

如果暴力求解的话,即每次枚举的时候都计算一遍元素和,那么总时间复杂度为 O ( W H ⋅ ( M − W + 1 ) ⋅ ( N − H + 1 ) ) = O ( W H M N ) O(WH\cdot(M-W+1)\cdot(N-H+1))=O(WHMN) O(WH(MW+1)(NH+1))=O(WHMN),不符合题意。

求区域的元素和可以使用「二维前缀和」算法,我们可以在 O ( M N ) O(MN) O(MN) 的时间内预处理出一个前缀和数组,然后每次枚举的时候只需要在 O ( 1 ) O(1) O(1) 的时间内就能算出子矩形的所有元素和,此时总时间复杂度为

O ( M N + ( M − W + 1 ) ⋅ ( N − H + 1 ) ) O(MN+(M-W+1)\cdot(N-H+1)) O(MN+(MW+1)(NH+1))

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/406882.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Win11搭建Angular开发环境

作为一名后端程序员&#xff0c;无论当前的工作是否需要&#xff0c;会一点点前端无疑对自己是有帮助的。今天就来介绍一下如何搭建Angular的开发环境。我也是摸着石头过河&#xff0c;所以很多东西也不熟悉&#xff0c;先按照Angular官网的介绍来配置吧。 这个是Angular最新版…

mmyolo训练模型报错:ValueError: Key img_path is not in available keys解决办法

使用mmyolo训练模型 的时候报错&#xff1a;ValueError: Key img_path is not in available keys. Traceback (most recent call last): File “tools/train.py”, line 123, in main() File “tools/train.py”, line 119, in main runner.train() File “/root/anaconda3/en…

erlang学习:erlang学习:书上案例22.6练习题3

初步实现了书上案例第二&#xff0c;三问的要求&#xff0c;对输出结果有部分偏差&#xff0c;没有实现对已完成任务状态的记录&#xff0c;因此已完成任务输出无论如何都是0&#xff0c;明天会在record中加一个字段进行已完成任务状态的记录 (2) 添加一个名为job_centre:stati…

服务器备份

服务器备份 一、方案 FreeFileSync freeSSHd Windows任务计划程序 FreeFileSync&#xff1a;设置文件备份方案&#xff08;双向同步、镜像同步、更新同步、自定义同步&#xff09;&#xff0c;适用于本地的文件同步之外&#xff0c;还支持 Google Driver、SFTP 和 FTP 三种…

泛微基于华为仓颉编程语言开发公文交换系统 推动办公软件全面国产化

2024年6月21日下午&#xff0c;华为终端BG软件部总裁龚体先生在华为开发者大会主题演讲《鸿蒙原生应用&#xff0c;全新出发&#xff01;》中向全球开发者介绍了华为自研仓颉编程语言&#xff0c;并发布了HarmonyOS NEXT仓颉语言开发者预览版。这是华为首次公开发布仓颉编程语言…

Windows—UDP编程

Client骨架&#xff1a; #include <iostream> #include <WinSock2.h> #pragma comment(lib,"ws2_32.lib")int main() {//启动Winsock DLLWORD wVersionRequested MAKEWORD(2, 2);WSADATA lpWSAData;WSAStartup(wVersionRequested, &lpWSAData);//…

实现AOP机制 + Spring总结

文章目录 1.目录2.SmartAnimal.java 接口&#xff08;JDK代理必须有接口&#xff09;3.SmartDog.java4.SmartAnimalAspect.java5.SunSpringApplicationContext.java1.在Bean的后置处理器之后使用动态代理2.完整代码 6.测试1.AppMain.java 调用被代理的类的方法2.结果 7.Spring底…

Unity抖音直播玩法开发流程

前言 近两年直播玩法逐渐新兴起来了&#xff0c;也出现不少质量还不错的作品&#xff0c;比如下列《红蓝对决》《三国全战》等。近期我们也做了一款直播玩法&#xff0c;就此记录下开发流程。 1&#xff0c;申请应用 进入抖音开发者平台&#xff0c;在首页入驻平台。 如果是…

Vue3+Vite 解决“找不到模块“@/components/xxx.vue”或其相应的类型声明 ts(2307)”

1. 安装插件 pnpm i types/node -D2. 修改vite.config.ts文件 import path from path;resolve: {alias: {"": path.resolve(__dirname,"./src"),},},3. 修改tsconfig.app.json文件 别人教的都是修改tsconfig.json文件&#xff0c;但是我发现可能是因为版…

写论文找不到灵感?ChatGPT能提供的一些帮助

学境思源&#xff0c;一键生成论文初稿&#xff1a; AcademicIdeas - 学境思源AI论文写作 在学术写作过程中&#xff0c;许多读者常常会面临一个问题——找不到灵感。面对庞大的文献和复杂的研究方向&#xff0c;往往感到无从下手。随着人工智能技术的发展&#xff0c;像ChatG…

redis面试(十九)读写锁ReadLock

读写锁ReadLock 简单来说就是互斥锁和非互斥锁。多个客户端可以同事加的锁叫读锁&#xff0c;只能有一个客户端加的锁叫写锁。这个理论应该是从数据库中来的&#xff0c;放在这里也是同样的解释。 多个客户端同时加读锁&#xff0c;是不会互斥的&#xff0c;多个客户端可以同…

“肯将玉钳作双戟,一舞天下定乾坤。”记唐铎《墨龙图》之中的笔墨画意

唐铎&#xff0c;1957 年生于北京&#xff0c;国家一级美术师&#xff0c;曾先后师从于刘文西、黄申发老师&#xff0c;原名唐京鸣&#xff0c;京城人士&#xff0c;取其名&#xff0c;不鸣则已&#xff0c;一鸣惊人之意&#xff0c;学画三十余年&#xff0c;专注于齐派虾蟹&am…

【技巧】-DNSlog外带文件

❤️博客主页&#xff1a; iknow181 &#x1f525;系列专栏&#xff1a; 网络安全、 Python、JavaSE、JavaWeb、CCNP &#x1f389;欢迎大家点赞&#x1f44d;收藏⭐评论✍ 1.什么是DNSlog 我们都知道DNS就是将域名解析为ip&#xff0c;用户在浏览器上输入一个域名A.com&#x…

深入探索分布式任务调度框架:MySQL实现高效锁机制

本文主要介绍项目中怎么使用 MySQL 实现分布式锁的 背景 假如我们现在要做一个高性能、可扩展的分布式任务调度框架&#xff0c;要怎么设计呢&#xff1f;下面是我之前自己设计的一个架构图。 为了方便后续的分布式锁的设计&#xff0c;我们大致描述下各个角色都做了哪些事情…

鹏哥C语言自定义笔记重点(29-)

29.函数指针数组 30.void指针是不能直接解引用&#xff0c;也不能-整数。 void*是无具体类型的指针&#xff0c;可以接受任何类型的地址。 31.qsort:使用快速排序的思想实现一个排序函数(升序) 32. 33.地址的字节是4/8 34.char arr[]{a,b} sizeof(arr[0]1)答案是4&#xff0…

Godot《躲避小兵》实战之游戏开始界面制作

我们的游戏还需要用户可操作的界面&#xff0c;比如开始游戏&#xff0c;退出以及显示分数等UI界面。 创建新场景&#xff0c;点击“其他节点”按钮&#xff0c;然后添加一个 CanvasLayer 节点并命名为 HUD。“HUD”是“heads-up display”&#xff08;游戏信息显示&#xff0…

windows所有功能都可使用就是电脑黑屏了

运行新任务然后输入explorer.exe勾选上创建任务确定就好了 下次尽量不手欠&#xff01;&#xff01;&#xff01;&#xff01;

Golang | Leetcode Golang题解之第367题有效的完全平方数

题目&#xff1a; 题解&#xff1a; func isPerfectSquare(num int) bool {x0 : float64(num)for {x1 : (x0 float64(num)/x0) / 2if x0-x1 < 1e-6 {x : int(x0)return x*x num}x0 x1} }

改编版猜数字小游戏,猜错了就黑屏(整蛊版本)

1. 前情提要 在前一篇博客中&#xff0c;我们了解到了如何获得随机数&#xff0c;并且通过运算可以规定所获得的这个随机数的范围在多少数值之间 那么接下来我们就需要去具体去实现猜数字游戏的各种布置 2. 布置主菜单 玩一个游戏&#xff0c;最开始的界面都会是一个主菜单…