目录
- 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 ∀i∈X,f(i)>i。
给定有序字符串 S S S,按照下述规则计算 S S S 的分数,设 P , Q P,Q P,Q 分别为有序字符串
- A B AB AB 的分数 = 1 =1 =1
- P Q PQ PQ 的分数 = = = P P P 的分数 + + + Q Q Q 的分数
- A P B APB APB 的分数 = = = 2 ⋅ P 2\cdot P 2⋅P 的分数
输入描述
输入一个仅包含 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 0→21→53→64→7
在这个映射下, 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 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 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((M−W+1)⋅(N−H+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⋅(M−W+1)⋅(N−H+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+(M−W+1)⋅(N−H+1))