鹽山網(wǎng)站開發(fā)百度競(jìng)價(jià)怎么做開戶需要多少錢

目錄
- 1. 第一題
- 2. 第二題
- 3. 論述題
? 時(shí)間:2024/08/18
🔄 輸入輸出:ACM格式
? 時(shí)長(zhǎng):2h
本試卷分為不定項(xiàng)選擇,編程題,必做論述題和選做論述題,這里只展示編程題和必做論述題,一共三道。
注意,虹軟的筆試題目表述的不太清晰,并且也沒(méi)有給出數(shù)據(jù)范圍,這里針對(duì)表述做了一些優(yōu)化。
1. 第一題
已知字符串 S S S 只包含 A , B A,B A,B 兩種字符,設(shè) 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,按照下述規(guī)則計(jì)算 S S S 的分?jǐn)?shù),設(shè) P , Q P,Q P,Q 分別為有序字符串
- A B AB AB 的分?jǐn)?shù) = 1 =1 =1
- P Q PQ PQ 的分?jǐn)?shù) = = = P P P 的分?jǐn)?shù) + + + Q Q Q 的分?jǐn)?shù)
- A P B APB APB 的分?jǐn)?shù) = = = 2 ? P 2\cdot P 2?P 的分?jǐn)?shù)
輸入描述
輸入一個(gè)僅包含 A , B A,B A,B 的字符串
輸出描述
輸出一個(gè)整數(shù)
題解
這道題本來(lái)就有些繞,再加上原本的表述不夠清晰,所以很容易誤解題意,博主這里稍微修改了下表述。
首先來(lái)看什么是有序字符串?這里舉一個(gè)例子。設(shè) 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}。我們可以找到一個(gè)雙射
0 → 2 1 → 5 3 → 6 4 → 7 0\to2\\ 1\to 5 \\ 3\to6\\ 4\to 7 0→21→53→64→7
在這個(gè)映射下, 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 是有序的。更通俗地來(lái)講,對(duì)于 S S S 中的每一個(gè) A A A,我們都要在 S S S 中找到一個(gè)與之配對(duì)的 B B B,使得 B B B 的索引大于 A A A 的索引,這樣的 S S S 才是有序字符串。
由于雙射的性質(zhì),易知 ∣ X ∣ = ∣ Y ∣ |X|=|Y| ∣X∣=∣Y∣,因此如果 S S S 是有序的,那么它的長(zhǎng)度一定是偶數(shù)。此外,一定有 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,若不然,假設(shè) S [ 0 ] = B S[0]=B S[0]=B,我們無(wú)法在 S S S 中找到與它配對(duì)的 A A A,使得 A A A 的下標(biāo)小于它,對(duì)于 S [ ? 1 ] S[-1] S[?1] 同理。設(shè) S S S 的長(zhǎng)度為 2 n , n = 1 , 2 , ? 2n,\;n=1,2,\cdots 2n,n=1,2,?,易知 n = 1 n=1 n=1 時(shí) S = A B S=AB S=AB,我們稱這樣的 S S S 為基本串(自己瞎起的名hh,方便后面講)。
現(xiàn)在回到一般情況,設(shè) S S S 的長(zhǎng)度為 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?}。假設(shè) X , Y X,Y X,Y 均是從左向右統(tǒng)計(jì)出來(lái)的,從而 X , Y X,Y X,Y 均是有序數(shù)組。容易得出以下結(jié)論:
S 是有序字符串 ? ? i , a i < b i S 是有序字符串 \Leftrightarrow \forall i,\,a_i<b_i S是有序字符串??i,ai?<bi?
充分性顯然,必要性用反證法證明。
從題中所給的信息,可以猜測(cè),以下兩個(gè)事件為對(duì)立事件(博主還沒(méi)有來(lái)得及證明,歡迎大家在評(píng)論區(qū)補(bǔ)充):
- S S S 可以拆成兩個(gè)有序字符串 P , Q P,Q P,Q,即 S = P Q S=PQ S=PQ。且拆法不會(huì)影響到 S S S 的分?jǐn)?shù)。
- S S S 可以拆成 A P B APB APB 的形式,其中 P P P 是有序的。
很明顯可以用遞歸來(lái)做,每次判斷當(dāng)前的 S S S 屬于以上哪一種情況,然后遞歸進(jìn)行求解, A B AB AB 的分?jǐn)?shù)為 1 1 1 可以作為遞歸終止條件。
以 S = A A B A A B B B S=AABAABBB S=AABAABBB 為例。顯然 S S S 不能拆成兩個(gè)有序字符串,因此將其表示成 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 不是有序的,根據(jù)之前的猜想, P P P 一定可以拆成兩個(gè)有序字符串 U , V U,V U,V,且拆法不會(huì)影響到最終分?jǐn)?shù)。很明顯 U = A B , V = A A B B U=AB,V=AABB U=AB,V=AABB。于是可以計(jì)算 S S S 的分?jǐn)?shù): 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;
}// 計(jì)算有序字符串s在閉區(qū)間[l, r]上的分?jǐn)?shù)
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)) {// 拆法不會(huì)影響分?jǐn)?shù),直接返回即可return score(s, l, i) + score(s, i + 1, r);}}// 因?yàn)槭菍?duì)立事件,所以直接返回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;
}
后續(xù)證明了猜想會(huì)在這里補(bǔ)充,也歡迎廣大網(wǎng)友補(bǔ)充。
2. 第二題
有紅、綠、藍(lán)三種顏色(分別用R、G、B表示)的小球,其數(shù)量分別為 a , b , c a,b,c a,b,c?,F(xiàn)在想將這些小球排成一列,但不希望相鄰的兩個(gè)小球出現(xiàn)相同顏色,請(qǐng)問(wèn)有多少種排列方法?
輸入描述
第一行為 a 、 b 、 c a、b、c a、b、c 對(duì)應(yīng)的三個(gè)數(shù)字,以空格隔開
輸出描述
輸出為排列方法的總數(shù)
題解
本題較為簡(jiǎn)單,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); // 選擇藍(lán)色}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 個(gè),綠球有 b b b 個(gè),藍(lán)球有 c c c 個(gè),且上一次放置的是 last
顏色的情況下,能夠放置的方法總數(shù)。初始時(shí)沒(méi)有放置,故 last == -1
。
考慮邊界條件。例如只有一個(gè)紅球的情況下,此時(shí)放置方案只有一種,因此
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. 論述題
假設(shè)有一張寬為 M M M,高為 N N N 的黑白圖像,每個(gè)元素都是 0 0 0 或 1 1 1,其中 0 0 0 表示黑色像素, 1 1 1 表示白色像素,要在該圖像中找到一個(gè)寬為 W W W,高為 H H H 的矩形子區(qū)域( W < M , H < N W<M,H<N W<M,H<N 且已知),使得該區(qū)域內(nèi)的白色像素?cái)?shù)最多,并計(jì)算該區(qū)域內(nèi)的白色像素?cái)?shù)。
注意 O ( M N H W ) O(MNHW) O(MNHW) 的實(shí)現(xiàn)不計(jì)分,請(qǐng)用文字描述或者偽代碼說(shuō)明算法過(guò)程,并分析時(shí)間復(fù)雜度。
題解
容易知道枚舉所有子矩形的時(shí)間復(fù)雜度為 O ( ( M ? W + 1 ) ? ( N ? H + 1 ) ) O((M-W+1)\cdot(N-H+1)) O((M?W+1)?(N?H+1))。
計(jì)算子矩形中的白色像素?cái)?shù)等價(jià)于計(jì)算子矩形中的所有元素和。
如果暴力求解的話,即每次枚舉的時(shí)候都計(jì)算一遍元素和,那么總時(shí)間復(fù)雜度為 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),不符合題意。
求區(qū)域的元素和可以使用「二維前綴和」算法,我們可以在 O ( M N ) O(MN) O(MN) 的時(shí)間內(nèi)預(yù)處理出一個(gè)前綴和數(shù)組,然后每次枚舉的時(shí)候只需要在 O ( 1 ) O(1) O(1) 的時(shí)間內(nèi)就能算出子矩形的所有元素和,此時(shí)總時(shí)間復(fù)雜度為
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))