2023年CCF非專業(yè)級別軟件能力認證第二輪 （CSP-S）提高級C++語言試題
編程題
第 1 題 ? ?問答題
密碼鎖（lock）
題目描述
小Y有一把五個撥圈的密碼鎖。如圖所示，每個撥圈上是從0到9的數字。每個撥圈都是從0到9的循環(huán)，即9撥動一個位置后可以變成0或8，

因為校園里比較安全，小Y采用的鎖車方式是：從正確密碼開始，隨機轉動密碼鎖僅一次；每次都是以某個幅度僅轉動一個撥圈或者同時轉動兩個相鄰的撥圈。當小Y選擇同時轉動兩個相鄰撥圈時，兩個撥圈轉動的幅度相同，即小Y可以將密碼鎖從00115轉成11115，但不會轉成12115。
時間久了，小Y也擔心這么鎖車的安全性，所以小Y記下了自己鎖車后密碼鎖的n個狀態(tài)，注意這n個狀態(tài)都不是正確密碼。
為了檢驗這么鎖車的安全性，小Y有多少種可能的正確密碼，使得每個正確密碼都能夠按照他所采用的鎖車方式產生鎖車后密碼鎖的全部n個狀態(tài)。
輸入格式
從文件lock.in中讀入數據。
輸入的第一行包含一個正整數n，表示鎖車后密碼鎖的狀態(tài)數。
接下來n行每行包含五個整數，表示一個密碼鎖的狀態(tài)。
輸出格式
輸出到文件lock.out中。
輸出一行包含一個整數，表示密碼鎖的這n個狀態(tài)按照給定的鎖車方式能對應多少種正確密碼。
樣例1輸入
1
0 0 1 1 5
樣例1輸出
81
樣例1解釋
一共有81種可能的方案。
其中轉動一個撥圈的方案有45種，轉動兩個撥圈的方案有36種。
樣例2
見選手目錄下的lock/lock2.in與lock/lock2.ans。

第 2 題 ? ?問答題
消消樂（game）
題目描述
小L現在在玩一個低配版本的消消樂，該版本的游戲是一維的，一次也只能消除兩個相鄰的元素。
現在，他有一個長度為n且僅由小寫字母構成的字符串。我們稱一個字符串是可消除的，當且僅當可以對這個字符串進行若干次操作，使之成為一個空字符串。
其中每次操作可以從字符串中刪除兩個相鄰的相同字符，操作后剩余字符串會拼接在一起。
小L想知道，這個字符串的所有非空連續(xù)子串中，有多少個是可消除的。
輸入格式
從文件game.in中讀入數據。
輸入的第一行包含一個正整數n，表示字符串的長度。
輸入的第二行包含一個長度為n且僅由小寫字母構成的的字符串，表示題目中詢問的字符串。
輸出格式
輸出到文件game.out中。
輸出一行包含一個整數，表示題目詢問的答案。
樣例1輸入
8
accabccb
樣例1輸出
5
樣例1解釋
一共有5個可消除的連續(xù)子串，分別是cc、acca、cc、bccb、accabccb。
樣例2
見選手目錄下的game/game2.in與game/game2.ans。
樣例3
見選手目錄下的game/game3.in與game/game3.ans。
樣例4
見選手目錄下的game/game4.in與game/game4.ans。

第 3 題 ? ?問答題
結構體（struct）
題目背景
在C++等高級語言中，除了int和float等基本類型外，通常還可以自定義結構體類型。在本題當中，你需要模擬一種類似C++的高級語言的結構體定義方式，并計算出相應的內存占用等信息。
題目描述
在這種語言中，基本類型共有4種：byte，short，int，long，分別占據1,2,4,8字節(jié)的空間。
定義一個結構體類型時，需要給出類型名和成員，其中每個成員需要按順序給出類.型和名稱。類型可以為基本類型，也可以為先.定義過的結構體類型。注意，定義結構體類型時不會定義具體元素，即不占用內存。
定義一個元素時，需要給出元素的類型和名稱。元素將按照以下規(guī)則占據內存：
? 元素內的所有成員將按照定義時給出的順序在內存中排布，對于類型為結構體的成員同理。
? 為了保證內存訪問的效率，元素的地址占用需要滿足對齊規(guī)則，即任何類型的大小和該類型元素在內存中的起始地址均應對齊到該類型對齊要求的整數倍。具體而言：
–對于基本類型：對齊要求等于其占據空間大小，如int類型需要對齊到4字節(jié)，其余同理。
–對于結構體類型：對齊要求等于其成員的對齊要求的最大值，如一個含有int和short的結構體類型需要對齊到4字節(jié)。
以下是一個例子（以C++語言的格式書寫）：
struct d {
? ? short a;
? ? int b;
? ? short c;
};
d e;
該代碼定義了結構體類型d與元素e。元素e包含三個成員e.a,e.b,e.c，分別占據第0～1，4～7，8～9字節(jié)的地址。由于類型d需要對齊到4字節(jié)，因此e占據了第0～11字節(jié)的地址，大小為12字節(jié)。
你需要處理n次操作，每次操作為以下四種之一：
1.定義一個結構體類型。具體而言，給定正整數k與字符串s,t1,n1,...,tk,nk，其中k表示該類型的成員數量，s表示該類型的類型名，t1,t2,...,tk按順序分別表示每個成員的類型，n1,n2,...,nk按順序分別表示每個成員的名稱。你需要輸出該結構體類型的大小和對齊要求，用一個空格分隔。
2.定義一個元素，具體而言，給定字符串t，n分別表示該元素的類型與名稱。所有被定義的元素將按順序，從內存地址為0開始依次排開，并需要滿足地址對齊規(guī)則。你需要輸出新定義的元素的起始地址。
3.訪問某個元素。具體而言，給定字符串s，表示所訪問的元素。與C++等語言相同，采用.來訪問結構體類型的成員。如a.b.c，表示a是一個已定義的元素，它是一個結構體類型，有一個名稱為b的成員，它也是一個結構體類型，有一個名稱為c的成員。你需要輸出如上被訪問的最內層元素的起始地址。
4.訪問某個內存地址。具體而言，給定非負整數addr，表示所訪問的地址，你需要判斷是否存在一個基本類型的元素占據了該地址。若是，則按操作3中的訪問元素格式輸出該元素；否則輸出ERR。
輸入格式
從文件struct.in中讀入數據。
第1行：一個正整數n，表示操作的數量。
接下來若干行，依次描述每個操作，每行第一個正整數op表示操作類型：
?若op=1，首先輸入一個字符串s與一個正整數k，表示類型名與成員數量，接下來k行每行輸入兩個字符串ti，ni，依次表示每個成員的類型與名稱。
?若op=2，輸入兩個字符串t，n，表示該元素的類型與名稱。
?若op=3，輸入一個字符串s，表示所訪問的元素。
?若op=4，輸入一個非負整數addr，表示所訪問的地址。
輸出格式
輸出到文件struct.out中。
輸出n行，依次表示每個操作的輸出結果，輸出要求如題目描述中所述。
樣例1輸入
5
1 a 2
short aa
int ab
1 b 2
a ba
long bb
2 b x
3 x.ba.ab
4 10
樣例1輸出
8 4
16 8
0
4
x.bb
樣例1解釋
結構體類型a中，int類型的成員aa占據第0～3字節(jié)地址，short類型的成員ab占據第4～5字節(jié)地址。又由于其對齊要求為4字節(jié)，可得其大小為8字節(jié)。由此可同理計算出結構體類型b的大小為16字節(jié)，對齊要求為8字節(jié)。
樣例2
見選手目錄下的struct/struct2.in與struct/struct2.ans。
樣例2解釋
第二個操作4中，訪問的內存地址恰好在為了地址對齊而留下的“洞”里，因此沒有基本類型元素占據它。
樣例3
見選手目錄下的struct/struct3.in與struct/struct3.ans。
數據范圍
對于全部數據，滿足1≤n≤100，1≤k≤100，0≤addr≤1018。
所有定義的結構體類型名、成員名稱和定義的元素名稱均由不超過10個字符的小
寫字母組成，且都不是byte,short,int,long（即不與基本類型重名）。
所有定義的結構體類型名和元素名稱互不相同，同一結構體內成員名稱互不相同。
但不同的結構體可能有相同的成員名稱，某結構體內的成員名稱也可能與定義的結構體或元素名稱相同。
保證所有操作均符合題目所述的規(guī)范和要求，即結構體的定義不會包含不存在的類型、不會訪問不存在的元素或成員等。
保證任意結構體大小及定義的元素占據的最高內存地址均不超過10^18。

特殊性質A：沒有操作1；
特殊性質B：只有一個操作1；
特殊性質C：所有操作1中給出的成員類型均為基本類型；
特殊性質D：基本類型只有l(wèi)ong。
提示
對于結構體類型的對齊要求和大小，形式化的定義方式如下：
?設該結構體內有k個成員，其大小分別為s1,...,sk，對齊要求分別為a1,...,ak；
?則該結構體的對齊要求為a=max{a1,...,ak}；
?再設這些成員排布時的地址偏移量分別為o1,...,ok，則：
–o1=0；
–對于i=2,...,k，oi為滿足oi?1+si?1≤oi且ai整除oi的最小值；
–則該結構體的大小s為滿足ok+sk≤s且a整除s的最小值；
對于定義元素時的內存排布，形式化的定義方式如下：
?設第i個被定義的元素大小為si，對齊要求為ai，起始地址為bi；
?則b1=0，對于2≤i，bi為滿足bi?1+si?1≤bi且ai整除bi的最小值。

第 4 題 ? ?問答題
種樹（tree）
題目描述
你是一個森林養(yǎng)護員，有一天，你接到了一個任務：在一片森林內的地塊上種樹，并養(yǎng)護至樹木長到指定的高度。
森林的地圖有n片地塊，其中1號地塊連接森林的入口。共有n?1條道路連接這些地塊，使得每片地塊都能通過道路互相到達。最開始，每片地塊上都沒有樹木。
你的目標是：在每片地塊上均種植一棵樹木，并使得i號地塊上的樹的高度生長到不低于ai米。
你每天可以選擇一個未種樹且與某個已種樹的地塊直接鄰接（即通過單條道路相.連）的地塊，種一棵高度為0米的樹。如果所有地塊均已種過樹，則你當天不進行任何操作。特別地，第1天你只能在1號空地種樹。
對每個地塊而言，從該地塊被種下樹的當天開始，該地塊上的樹每天都會生長一定的高度。由于氣候和土壤條件不同，在第x天，i號地塊上的樹會長高max(bi+x?ci,1)
米。注意這里的x是從整個任務的第一天，而非種下這棵樹的第一天開始計算。
你想知道：最少需要多少天能夠完成你的任務？
輸入格式
從文件tree.in中讀入數據。
輸入的第一行包含一個正整數n，表示森林的地塊數量。
接下來n行：每行包含三個整數ai,bi,ci，分別描述一片地塊，含義如題目描述中所述。
接下來n?1行：每行包含兩個正整數ui,vi，表示一條連接地塊ui和vi的道路。
輸出格式
輸出到文件tree.out中。
輸出一行僅包含一個正整數，表示完成任務所需的最少天數。
樣例1輸入
4
12 1 1
2 4 ‐1
10 3 0
7 10 ‐2
1 2
1 3
3 4
樣例1輸出
1 5
樣例1解釋
第1天：在地塊1種樹，地塊1的樹木長高至2米。
第2天：在地塊3種樹，地塊1,3的樹木分別長高至5,3米。
第3天：在地塊4種樹，地塊1,3,4的樹木分別長高至9,6,4米。
第4天：在地塊2種樹，地塊1,2,3,4的樹木分別長高至14,1,9,6米。
第5天：地塊1,2,3,4的樹木分別長高至20,2,12,7米。
樣例2
見選手目錄下的tree/tree2.in與tree/tree2.ans。
樣例3
見選手目錄下的tree/tree3.in與tree/tree3.ans。
樣例4
見選手目錄下的tree/tree4.in與tree/tree4.ans。
數據范圍
對于所有測試數據有：1≤n≤105，1≤ai≤1018,1≤bi≤109，0≤|ci|≤109，1≤ui,vi≤n。

保證存在方案能在109天內完成任務
特殊性質A：對于所有1≤i≤n，均有ci=0；
特殊性質B：對于所有1≤i<n，均有ui=i，vi=i+1；
特殊性質C：與任何地塊直接相連的道路均不超過2條；
特殊性質D：對于所有1≤i<n，均有ui=1。

更多歷年真題請查看網站：

網站鏈接?

青少年軟件編程歷年真題模擬題實時更新