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

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

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

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

1. 第一题

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

• $X$ 与 $Y$ 之间存在双射 $f$，满足 $\forall i\in X,f(i)>i$。

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

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

输入描述

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

输出描述

输出一个整数

题解

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

首先来看什么是有序字符串？这里举一个例子。设 $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}。我们可以找到一个双射

$$\begin{gathered} 0\to 2 \\ 1\to 5 \\ 3\to 6 \\ 4\to 7 \end{gathered}$$

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

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

现在回到一般情况，设 $S$ 的长度为 $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$ 均是有序数组。容易得出以下结论：

$$S是有序字符串\iff \forall i,a_i<b_i$$

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

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

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

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

以 $S=AABAABBB$ 为例。显然 $S$ 不能拆成两个有序字符串，因此将其表示成 $APB$ 的形式，其中 $P=ABAABB$ 是一定是有序字符串。如果将 $P$ 拆成 $ARB$ 的形式，由于 $R=BAAB$ 不是有序的，根据之前的猜想，$P$ 一定可以拆成两个有序字符串 $U,V$，且拆法不会影响到最终分数。很明显 $U=AB,V=AABB$。于是可以计算 $S$ 的分数：$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$ 对应的三个数字，以空格隔开

输出描述

输出为排列方法的总数

题解

本题较为简单，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$ 个，绿球有 $b$ 个，蓝球有 $c$ 个，且上一次放置的是 last 颜色的情况下，能够放置的方法总数。初始时没有放置，故 last == -1。

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

$$1=dfs(1,0,0,-1)=dfs(0,0,0,0)$$

故可知边界条件 $dfs(0,0,0,last)=1$。

3. 论述题

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

题解

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

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

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

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

$$O(MN+(M-W+1)\cdot (N-H+1))$$