? 時(shí)間：2024/08/18
🔄 輸入輸出：ACM格式
? 時(shí)長(zhǎng)：2h

本試卷分為不定項(xiàng)選擇，編程題，必做論述題和選做論述題，這里只展示編程題和必做論述題，一共三道。

注意，虹軟的筆試題目表述的不太清晰，并且也沒(méi)有給出數(shù)據(jù)范圍，這里針對(duì)表述做了一些優(yōu)化。

1. 第一題

已知字符串 $S$ 只包含 $A,B$ 兩種字符，設(shè) $X$ 為 $S$ 中所有 $A$ 的索引的集合，$Y$ 為 $S$ 中所有 $B$ 的索引的集合。若 $S$ 滿足以下條件，則稱 $S$ 為有序字符串。

• $X$ 與 $Y$ 之間存在雙射 $f$，滿足 $?i\in X,f(i)>i$。

給定有序字符串 $S$，按照下述規(guī)則計(jì)算 $S$ 的分?jǐn)?shù)，設(shè) $P,Q$ 分別為有序字符串

1. $AB$ 的分?jǐn)?shù) $=1$
2. $PQ$ 的分?jǐn)?shù) $=$ $P$ 的分?jǐn)?shù) $+$ $Q$ 的分?jǐn)?shù)
3. $APB$ 的分?jǐn)?shù) $=$ $2?P$ 的分?jǐn)?shù)

輸入描述

輸入一個(gè)僅包含 $A,B$ 的字符串

輸出描述

輸出一個(gè)整數(shù)

題解

這道題本來(lái)就有些繞，再加上原本的表述不夠清晰，所以很容易誤解題意，博主這里稍微修改了下表述。

首先來(lái)看什么是有序字符串？這里舉一個(gè)例子。設(shè) $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è)雙射

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

在這個(gè)映射下，$2>0,5>1,6>3,7>4$，因此 $S$ 是有序的。更通俗地來(lái)講，對(duì)于 $S$ 中的每一個(gè) $A$，我們都要在 $S$ 中找到一個(gè)與之配對(duì)的 $B$，使得 $B$ 的索引大于 $A$ 的索引，這樣的 $S$ 才是有序字符串。

由于雙射的性質(zhì)，易知 $|X|=|Y|$，因此如果 $S$ 是有序的，那么它的長(zhǎng)度一定是偶數(shù)。此外，一定有 $S[0]=A,S[?1]=B$，即 $S$ 的首字符一定是 $A$，尾字符一定是 $B$，若不然，假設(shè) $S[0]=B$，我們無(wú)法在 $S$ 中找到與它配對(duì)的 $A$，使得 $A$ 的下標(biāo)小于它，對(duì)于 $S[?1]$ 同理。設(shè) $S$ 的長(zhǎng)度為 $2n,n=1,2,?$，易知 $n=1$ 時(shí) $S=AB$，我們稱這樣的 $S$ 為基本串（自己瞎起的名hh，方便后面講）。

現(xiàn)在回到一般情況，設(shè) $S$ 的長(zhǎng)度為 $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$ 均是從左向右統(tǒng)計(jì)出來(lái)的，從而 $X,Y$ 均是有序數(shù)組。容易得出以下結(jié)論：

$$S是有序字符串??i,a_i<b_i$$

充分性顯然，必要性用反證法證明。

從題中所給的信息，可以猜測(cè)，以下兩個(gè)事件為對(duì)立事件（博主還沒(méi)有來(lái)得及證明，歡迎大家在評(píng)論區(qū)補(bǔ)充）：

• $S$ 可以拆成兩個(gè)有序字符串 $P,Q$，即 $S=PQ$。且拆法不會(huì)影響到 $S$ 的分?jǐn)?shù)。
• $S$ 可以拆成 $APB$ 的形式，其中 $P$ 是有序的。

很明顯可以用遞歸來(lái)做，每次判斷當(dāng)前的 $S$ 屬于以上哪一種情況，然后遞歸進(jìn)行求解， $AB$ 的分?jǐn)?shù)為 $1$ 可以作為遞歸終止條件。

以 $S=AABAABBB$ 為例。顯然 $S$ 不能拆成兩個(gè)有序字符串，因此將其表示成 $APB$ 的形式，其中 $P=ABAABB$ 是一定是有序字符串。如果將 $P$ 拆成 $ARB$ 的形式，由于 $R=BAAB$ 不是有序的，根據(jù)之前的猜想，$P$ 一定可以拆成兩個(gè)有序字符串 $U,V$，且拆法不會(huì)影響到最終分?jǐn)?shù)。很明顯 $U=AB,V=AABB$。于是可以計(jì)算 $S$ 的分?jǐn)?shù)：$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$?，F(xiàn)在想將這些小球排成一列，但不希望相鄰的兩個(gè)小球出現(xiàn)相同顏色，請(qǐng)問(wèn)有多少種排列方法?

輸入描述

第一行為 對(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$ 個(gè)，綠球有 $b$ 個(gè)，藍(lán)球有 $c$ 個(gè)，且上一次放置的是 last 顏色的情況下，能夠放置的方法總數(shù)。初始時(shí)沒(méi)有放置，故 last == -1。

考慮邊界條件。例如只有一個(gè)紅球的情況下，此時(shí)放置方案只有一種，因此

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

故可知邊界條件 $dfs(0,0,0,last)=1$。

3. 論述題

假設(shè)有一張寬為 $M$，高為 $N$ 的黑白圖像，每個(gè)元素都是 $0$ 或 $1$，其中 $0$ 表示黑色像素，$1$ 表示白色像素，要在該圖像中找到一個(gè)寬為 $W$，高為 $H$ 的矩形子區(qū)域（$W<M,H<N$ 且已知），使得該區(qū)域內(nèi)的白色像素?cái)?shù)最多，并計(jì)算該區(qū)域內(nèi)的白色像素?cái)?shù)。
注意 $O(MNHW)$ 的實(shí)現(xiàn)不計(jì)分，請(qǐng)用文字描述或者偽代碼說(shuō)明算法過(guò)程，并分析時(shí)間復(fù)雜度。

題解

容易知道枚舉所有子矩形的時(shí)間復(fù)雜度為 $O((M?W+1)?(N?H+1))$。

計(jì)算子矩形中的白色像素?cái)?shù)等價(jià)于計(jì)算子矩形中的所有元素和。

如果暴力求解的話，即每次枚舉的時(shí)候都計(jì)算一遍元素和，那么總時(shí)間復(fù)雜度為 $O(WH?(M?W+1)?(N?H+1))=O(WHMN)$，不符合題意。

求區(qū)域的元素和可以使用「二維前綴和」算法，我們可以在 $O(MN)$ 的時(shí)間內(nèi)預(yù)處理出一個(gè)前綴和數(shù)組，然后每次枚舉的時(shí)候只需要在 $O(1)$ 的時(shí)間內(nèi)就能算出子矩形的所有元素和，此時(shí)總時(shí)間復(fù)雜度為

$$O(MN+(M?W+1)?(N?H+1))$$