C/C++描述 第十一屆藍橋杯省賽C/C++大學B組 第一場(2020.7.5) 題目+題解

C/C++描述 第十一屆藍橋杯省賽C/C++大學B組 第一場(2020.7.5) 題目+題解

C/C++描述 第十一屆藍橋杯省賽C/C++大學B組

• • 試題 A: 指數計算
  • 試題 A 題解
  • 試題 B: 解密
  • 試題 B 題解
  • 試題 C: 跑步訓練
  • 試題 C 題解
  • 試題 D: 合并檢測
  • 試題D 題解
  • 試題 E: REPEAT 程式
  • 試題 E 答案
  • 試題 F: 分類計數
  • 試題F 題解
  • 試題 G: 整除序列
  • 試題G 題解
  • 試題 H: 走方格
  • 試題H 題解
  • 試題 I: 字元串編碼
  • 試題I 題解
  • 試題 J: 整數小拼接

本題總分：5 分

【問題描述】

7 月 1 日是建黨日，從 1921 年到 2020 年，中國共黨已經帶領中國人民

走過了 99 年。

請計算：7 ^ 2020 mod 1921，其中 A mod B 表示 A 除以 B 的餘數。

【答案送出】

這是一道結果填空題，你隻需要算出結果後送出即可。本題的結果為一個

整數，在送出答案時隻填寫這個整數，填寫多餘的内容将無法得分。

第一題不搞那些花裡胡哨的技巧，看到這種花裡胡哨的題目，直接打開機器上的Python環境，直接算

print((7**2020)%1921)
           

答案為：

480

小明設計了一種文章加密的方法：對于每個字母 c，将它變成某個另外的

字元 Tc。下表給出了字元變換的規則：

字母c	Tc
a	y	n	l	A	Y	N	L
b	x	o	g	B	X	O	G
c	m	p		C	M	P
d		q	u	D		Q	U
e		r	f	E		R	F
		s				S
	i	t	z		I	T	Z
h	k			H	K
		v	w			V	W
j				J

例如，将字元串 YeRi 加密可得字元串 EaFn。

小明有一個随機的字元串，加密後為

EaFnjISplhFviDhwFbEjRjfIBBkRyY

（由 30 個大小寫英文字母組成，不包含換行符），請問原字元串是多少？

（如果你把以上字元串和表格複制到文本檔案中，請務必檢查複制的内容

是否與文檔中的一緻。在試題目錄下有一個檔案 str.txt，第一行為上面的字元

串，後面 52 行依次為表格中的内容。）

隻包含 30 個大小寫英文字母的字元串，在送出答案時隻填寫這個字元串，填寫

多餘的内容将無法得分。

這裡如果有src.txt這個檔案的話，可以直接寫個Python程式，讀入後輸入EaFnjISplhFviDhwFbEjRjfIBBkRyY，找出原字元即可。

這裡我沒那個檔案，就直接複制表格了，粘貼的時候發現還是一行一行的來的，不過沒關系，這個字元串直接處理了就好了，Python程式為：

s = 'aynlAYNLbxogBXOGcmpoCMPOddquDDQUearfEARFfcssFCSSgitzGITZhkupHKUPinvwINVWjtwbJTWBkjxrKJXRlhyeLHYEmqzvMQZV'
dir = {}
for i in range(len(s)):
    if(i%2 == 1):
        dir[s[i]] = s[i-1]
a = 'EaFnjISplhFviDhwFbEjRjfIBBkRyY'
for item in a:
    print(dir[item],end='',sep='')
           

YeRikGSunlRzgDlvRwYkXkrGWWhXaA

本題總分：10 分

小明要做一個跑步訓練。

初始時，小明充滿體力，體力值計為 10000。如果小明跑步，每分鐘損耗

600 的體力。如果小明休息，每分鐘增加 300 的體力。體力的損耗和增加都是

均勻變化的。

小明打算跑一分鐘、休息一分鐘、再跑一分鐘、再休息一分鐘……如此循

環。如果某個時刻小明的體力到達 0，他就停止鍛煉。

請問小明在多久後停止鍛煉。為了使答案為整數，請以秒為機關輸出答案。

答案中隻填寫數，不填寫機關。

這裡可以口算：答案為：

3880

10000 / (600-300) == 33.33
33*(600-300) = 9900
10000 - 9900 + 300 = 400 < 600
是以時間為32*2*60 + 400/10 = 3880
           

也可以寫程式模拟:

energy = 10000
min = 0
second = 0
while(energy):
    min += 1
    if min % 2 == 1:
        if energy > 600 :
            energy -= 600
        else:
            min -= 1
            second = energy/10
            energy = 0
    else:
        energy += 300
    if energy <= 0:
        break
print(min*60+second)

           

答案：

3380

新冠疫情由新冠病毒引起，最近在 A 國蔓延，為了盡快控制疫情，A 國準

備給大量群眾進病毒核酸檢測。

然而，用于檢測的試劑盒緊缺。

為了解決這一困難，科學家想了一個辦法：合并檢測。即将從多個人（k

個）采集的标本放到同一個試劑盒中進行檢測。如果結果為陰性，則說明這 k

個人都是陰性，用一個試劑盒完成了 k 個人的檢測。如果結果為陽性，則說明

至少有一個人為陽性，需要将這 k 個人的樣本全部重新獨立檢測（從理論上看，

如果檢測前 k 1 個人都是陰性可以推斷出第 k 個人是陽性，但是在實際操作中

不會利用此推斷，而是将 k 個人獨立檢測），加上最開始的合并檢測，一共使用

了 k + 1 個試劑盒完成了 k 個人的檢測。

A 國估計被測的群眾的感染率大概是 1%，呈均勻分布。請問 k 取多少能

最節省試劑盒？

這題數學問題
設總人數為pop,感染率p,每次k人，總市級數sum
sum = ([pop/k]+1)*(1+k*p(k+1))
這裡的[pop/k]+1)即pop/k向上取整
[pop/k]+1)這裡由于pop數量較大，是以這裡向上取整的1可以忽略，這裡直接取了pop/k，即
sum = (pop/k)*(1+kp(k+1))
将p代入sum = (pop/k)*(1+k*0.01(k+1))
sum求導 = (pop/k)(0.01k-1/k)
可得當k = 10時，sum取最小值
是以K = 10
           

10

本題總分：15 分

附件 prog.txt 中是一個用某種語言寫的程式。

其中 REPEAT k 表示一個次數為 k 的循環。循環控制的範圍由縮進表達，

從次行開始連續的縮進比該行多的（前面的空白更長的）為循環包含的内容。

例如如下片段：

REPEAT 2:

​ A = A + 4

​ REPEAT 5:

​ REPEAT 6:

​ A = A + 5

​ A = A + 7

​ A = A + 8

A = A + 9

A = A + 4 所在的行到 A = A + 8 所在的行都在第一行的

循環兩次中。

REPEAT 6: 所在的行到 A = A + 7 所在的行都在 REPEAT 5: 循環中。

A = A + 5 實際總共的循環次數是 2 × 5 × 6 = 60 次。

請問該程式執行完畢之後，A 的值是多少？

這題直接按流程算也挺簡單

未說A初值，這裡預設為0
REPEAT 6循環執行一次，A+30
REPEAT 5循環執行一次，A+185
REPEAT 2循環一次，A+4+185+8 = A+197
REPEAT 2循環後，A+394
最終：A+403
           

403

時間限制: 1.0s 記憶體限制: 512.0MB 本題總分：15 分

輸入一個字元串，請輸出這個字元串包含多少個大寫字母，多少個小寫字

母，多少個數字。

【輸入格式】

輸入一行包含一個字元串。

【輸出格式】

輸出三行，每行一個整數，分别表示大寫字母、小寫字母和數字的個數。

【樣例輸入】

1+a=Aab

【樣例輸出】

1

3

【評測用例規模與約定】

對于所有評測用例，字元串由可見字元組成，長度不超過 100。

C/C++描述程式為：

#include <iostream>
using namespace std;
int main(){
    string in;
    cin>>in;
    int num_digital,num_capital,num_lowercase;//數字，大寫字母，小寫字母的數量
    num_capital = num_digital = num_lowercase = 0;
    int len_in = in.length();
    for(int i = 0;i < len_in;i++){
        if(in[i] <= '9' && in[i] >= '0')
            num_digital++;
        if((in[i] <= 'Z' && in[i] >= 'A'))
            num_capital++;
        if(in[i] <= 'z' && in[i] >= 'a')
            num_lowercase++;
    }
    cout<<num_capital<<endl<<num_lowercase<<endl<<num_digital;
    return 0;
}
           

時間限制: 1.0s 記憶體限制: 512.0MB 本題總分：20 分

有一個序列，序列的第一個數是 n，後面的每個數是前一個數整除 2，請輸

出這個序列中值為正數的項。

輸入一行包含一個整數 n。

輸出一行，包含多個整數，相鄰的整數之間用一個空格分隔，表示答案。

20

20 10 5 2 1

對于 80% 的評測用例，1 ≤ n ≤ 109。

對于所有評測用例，1 ≤ n ≤ 1018。

我有點懷疑這是不是藍橋杯的題目了

#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    while(n){
        cout<<n<<" ";
        n/=2;
    }
    return 0;
}
           

在平面上有一些二維的點陣。

這些點的編号就像二維數組的編号一樣，從上到下依次為第 1 至第 n 行，

從左到右依次為第 1 至第 m 列，每一個點可以用行号和列号來表示。

現在有個人站在第 1 行第 1 列，要走到第 n 行第 m 列。隻能向右或者向下

走。

注意，如果行号和列數都是偶數，不能走入這一格中。

問有多少種方案。

輸入一行包含兩個整數 n, m。

輸出一個整數，表示答案。

3 4

2

6 6

對于所有評測用例，1 ≤ n ≤ 30, 1 ≤ m ≤ 30。

這題的這個資料量。。。直接暴力就完了，到這裡我已經嚴重懷疑我拿到的是不是藍橋杯的題目了。。。

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> dp(n+1,vector<int>(m+1));
    for(int i = 1;i <= n;i++){
        dp[i][1] = 1;
    }
    for (int j = 1; j <= m; ++j) {
        dp[1][j] = 1;
    }
    for(int i = 2;i <= n;i++){
        for (int j = 2; j <= m; ++j) {
            if(i%2==0 && j%2==0)
                continue;
            else
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    cout<<dp[n][m];
    return 0;
}
           

時間限制: 1.0s 記憶體限制: 512.0MB 本題總分：25 分

小明發明了一種給由全大寫字母組成的字元串編碼的方法。對于每一個大

寫字母，小明将它轉換成它在 26 個英文字母中序号，即 A → 1, B → 2, … Z →

26。

這樣一個字元串就能被轉化成一個數字序列：

比如 ABCXYZ → 123242526。

現在給定一個轉換後的數字序列，小明想還原出原本的字元串。當然這樣

的還原有可能存在多個符合條件的字元串。小明希望找出其中字典序最大的字

符串。

一個數字序列。

一個隻包含大寫字母的字元串，代表答案

123242526

LCXYZ

對于 20% 的評測用例，輸入的長度不超過 20。

對于所有評測用例，輸入的長度不超過 200000。

#include <iostream>
#include <vector>
using namespace std;
int main(){
    string in ;
    cin>>in;
    int len = in.length();
    string re = "";
    int flag_1;//第一位為1
    int flag_2;//第一位為2
    flag_1 = flag_2 = 0;
    for(int i = 0;i < len;i++){
        if(flag_1){
            int mid = int(in[i-1]-'0')*10+int(in[i]-'0');
            re += char(mid+'A'-1);
            flag_1 = 0;
            continue;
        }
        if(flag_2){
            if(in[i]<='6'){
                int mid = int(in[i-1]-'0')*10+int(in[i]-'0');
                re += char(mid+'A'-1);
                flag_2 = 0;
            } else{
                re += char(in[i-1] - '0' +'A'-1);
                re += char(in[i] - '0' +'A'-1);
                flag_2 = 0;
            }
            continue;
        }
        if(in[i] >= '3')
            re += char(in[i] - '0' + 'A' - 1);
        if(in[i] == '1' ){
            if(i+2<=len-1 && in[i] == '0'){
                re += char(in[i] - '0' + 'A' - 1);
                continue;
            }
            flag_1 = 1;
        }
        if(in[i] == '2'){
            if(i+2<=len-1 && in[i] == '0'){
                re += char(in[i] - '0' + 'A' - 1);
                continue;
            }
            flag_2 = 1;
        }
    }
    cout<<re;
    return 0;
}
           

給定義個長度為 n 的數組 A1, A2, · · · , An。你可以從中選出兩個數 Ai 和 Aj (i 不等于 j)，然後将 Ai 和 Aj 一前一後拼成一個新的整數。例如 12 和 345 可

以拼成 12345 或 34512 。注意交換 Ai 和 Aj 的順序總是被視為 2 種拼法，即便

是 Ai = Aj 時。

請你計算有多少種拼法滿足拼出的整數小于等于 K。

第一行包含 2 個整數 n 和 K。

第二行包含 n 個整數 A1, A2, · · · , An。

一個整數代表答案。

4 33

1 2 3 4

8