公司建设网站属于什么费用,h5 网站建设,做网站哪个平台,wordpress 咚门目录 1. 第一题2. 第二题3. 论述题 ⏰ 时间#xff1a;2024/08/18 #x1f504; 输入输出#xff1a;ACM格式 ⏳ 时长#xff1a;2h 本试卷分为不定项选择#xff0c;编程题#xff0c;必做论述题和选做论述题#xff0c;这里只展示编程题和必做论述题#xff0c;一共三… 目录 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 SAABAABBB SAABAABBB 从而 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 20,51,63,74 20,51,63,74因此 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,\;n1,2,\cdots 2n,n1,2,⋯易知 n 1 n1 n1 时 S A B SAB SAB我们称这样的 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_ib_i S是有序字符串⇔∀i,aibi
充分性显然必要性用反证法证明。
从题中所给的信息可以猜测以下两个事件为对立事件博主还没有来得及证明欢迎大家在评论区补充 S S S 可以拆成两个有序字符串 P , Q P,Q P,Q即 S P Q SPQ SPQ。且拆法不会影响到 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 SAABAABBB SAABAABBB 为例。显然 S S S 不能拆成两个有序字符串因此将其表示成 A P B APB APB 的形式其中 P A B A A B B PABAABB PABAABB 是一定是有序字符串。如果将 P P P 拆成 A R B ARB ARB 的形式由于 R B A A B RBAAB RBAAB 不是有序的根据之前的猜想 P P P 一定可以拆成两个有序字符串 U , V U,V U,V且拆法不会影响到最终分数。很明显 U A B , V A A B B UAB,VAABB UAB,VAABB。于是可以计算 S S S 的分数 S 2 P 2 ( U V ) 2 ( 1 2 ) 6 S2P2(UV)2(12)6 S2P2(UV)2(12)6。
#include bits/stdc.husing namespace std;bool is_ordered(const string s, int l, int r) {vectorint 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.husing 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 ) 1dfs(1,0,0,-1)dfs(0,0,0,0) 1dfs(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 WM,HN WM,HN 且已知使得该区域内的白色像素数最多并计算该区域内的白色像素数。 注意 O ( M N H W ) O(MNHW) O(MNHW) 的实现不计分请用文字描述或者伪代码说明算法过程并分析时间复杂度。
题解
容易知道枚举所有子矩形的时间复杂度为 O ( ( M − W 1 ) ⋅ ( N − H 1 ) ) O((M-W1)\cdot(N-H1)) O((M−W1)⋅(N−H1))。
计算子矩形中的白色像素数等价于计算子矩形中的所有元素和。
如果暴力求解的话即每次枚举的时候都计算一遍元素和那么总时间复杂度为 O ( W H ⋅ ( M − W 1 ) ⋅ ( N − H 1 ) ) O ( W H M N ) O(WH\cdot(M-W1)\cdot(N-H1))O(WHMN) O(WH⋅(M−W1)⋅(N−H1))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-W1)\cdot(N-H1)) O(MN(M−W1)⋅(N−H1))
