欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 新闻 > 焦点 > 虹软科技25届校招笔试算法 A卷

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

2024/12/28 9:21:54 来源:https://blog.csdn.net/raelum/article/details/141301777  浏览:    关键词:虹软科技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))

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com