.在C++中，下面哪個關鍵字用于聲明一個變量，其值不能被修改? ( )

A. unsigned

B. const

C. static

D. mutable

【答案】B

【考點】考點: C++語法知識: 變量與常量

【解析】變量是存儲信息的容器，變量在計算機內有一個內存地址，里面放的內容即變量的值，變量是允許被修改，但是常量的值不允許被修改，常量的定義格式如下:

const 數據類型 常量名 = 常量值;

數據類型 const 常量名 = 常量值;

題目說其值不能被修改指的是常量，因此選擇 const 修飾，所以答案選擇 B。

2. 八進制數 12345670 和 07654321 的和為 ( )

A. 22222221

B. 21111111

C. 22111111

D. 22222211

【答案】D

【考點】進制轉換 (初賽集訓內容)

【解析】R 進制的運算逢 R 進一，題目是八進制加法，所以每一個進制位上的數字是逢 8 進一。

12345670

+ 07654321

--------------

22222211

3. 閱讀下述代碼，請問修改 data 的 value 成員以存儲 3.14，正確的方式是( )

union Data{
    int num;
    float value;
    char symbol;
};
union Data data;

A. data.value = 3.14;

B. value.data = 3.14;

C. data->value = 3.14;

D. value->data = 3.14;

【答案】A

【考點】聯合體(NOI新大綱內容)

【解析】共用體定義格式:

union 共用體名{
    成員列表
};

共用體的所有成員占用同一段內存，修改一個成員會影響其余所有成員。

共用體占用的內存等于最長的成員占用的內存。

共用體使用了內存覆蓋技術，同一時刻只能保存一個成員的值，如果對新的成員賦值，就會把原來成員的值覆蓋掉。

題目中 data 占用 4 個字節，修改 value 使用 . 運算符，-> 適用于指針。

4. 假設有一個鏈表的節點定義如下：

struct Node {    int data;         Node* next;};

現在有一個指向鏈表頭部的指針：Node* head。如果想要在鏈表中插入一個新節點，其成員 data 的值為 42，并使新節點成為鏈表的第一個節點，下面哪個操作是正確的? ( )

A. Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;
B. Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
C. Node* newNode = new Node; newNode->data = 42; head->next = newNode;
D. Node* newNode = new Node; newNode->data = 42; newNode->next = head;

【答案】A

【考點】鏈表的插入(數據結構)

【解析】題目使用頭插法即可

B. 賦值錯誤。

C. 新插入的結點的后繼未確認。

D. 表頭結點的后繼未指向新生成的結點。

5. 根節點的高度為 1，一根擁有 2023 個節點的三叉樹高度至少為 ( )

A. 6

B. 7

C. 8

D. 9

【答案】C

【考點】樹

【解析】觀察下圖

第 1 層有 1 個結點

第 2 層有 3 個結點

第 3 層有 27 個結點

......

第 n 層有 3n 個結點

根據性質知道是一個等比數列，公比為 3，根據等比數列求和公式:

計算過程如下:

6. 小明在某一天中依次有七個空閑時間段，他想要選出至少一個空閑時間段來練習唱歌，但他希望任意兩個練習的時間段之間都有至少兩個空閑的時間段讓他休息，則小明一共有（ ）種選擇時間段的方案。

A. 31

B. 18

C. 21

D. 33

【答案】B

【考點】枚舉法

【解析】枚舉的方法講解

① 只有一個練習時間段的情況

② 只有兩個練習時間段的情況

③ 只有三個練習時間段的情況

7. 以下關于高精度運算的說法錯誤的是( )

A. 高精度計算主要是用來處理大整數或需要保留多位小數的運算

B. 大整數除以小整數的處理的步驟可以是，將被除數和除數對齊，從左到右逐位嘗試將除數乘以某個數，通過減法得到新的被除數，并累加商

C. 高精度乘法的運算時間只與參與運算的兩個整數中長度較長者的位數有關。

D. 高精度加法運算的關鍵在于逐位相加并處理進位。

【答案】C

【考點】高精度運算

【解析】高精度乘法的時間取決于兩個大整數的長度的乘積有關，高精度乘低精度 O(n) 的時間復雜度，高精度乘高精度 O(n*n) 的時間復雜度。

8. 后綴表達式“6 2 3 + - 3 8 2 / + * 2 ^ 3 +”對應的中綴表達式是 ( )

A. ((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3

B. 6 - 2 + 3 * 3 + 8 / 2 ^ 2 + 3

C. (6 - (2 + 3)) * ((3 + 8 / 2) ^ 2) + 3

D. 6 - ((2 + 3) * (3 + 8 / 2)) ^ 2 + 3

【答案】A

【考點】棧的應用

【解析】首先 6，2，3 入棧，遇到第一個操作符 +，彈出 2 和 3 執行加法，然后將 2 + 3 的結果入棧，遇到操作符 -，彈出兩個數 6 和 (2 + 3) 執行減法，然后將 (6 - (2 + 3)) 的結果入棧，3，8，2 依次入棧，遇到操作符 /，彈出 2 和 8 執行除法，然后將 8/2 入棧，遇到操作符 +，彈出 8/2 和 3 執行加法，然后將 (3 + 8/2) 入棧，遇到操作符 *，彈出 (6 - (2 + 3)) 和 (3 + 8/2) 執行乘法，然后將 (6-(2 + 3))*(3 + 8/2) 入棧，然后 2 入棧，遇到操作符 ^ 彈出 2 和 (6-(2 + 3))*(3 + 8/2) 執行異或操作，然后將 (6-(2 + 3))*(3 + 8/2)^2 入棧，然后 3 入棧，遇到操作符 +，然后彈出 3 和 (6-(2 + 3))*(3 + 8/2)^2 執行加法，然后將 (6-(2 + 3))*(3 + 8/2)^2 + 3 入棧，所以最終結果選 A。

9. 二進制數 101010 和 八進制數 166 的和為( )

A. 二進制數 10110000

B. 八進制數 236

C. 十進制數 158

D. 十六進制數 A0

【答案】D

【考點】進制轉換

【解析】先將二進制數和八進制數轉換成十進制

160 轉換成16進制是 A0，八進制是 240，二進制數是 10100000。

10. 假設有一組字符 {a,b,c,d,e,f}，對應的頻率分別為 5%，9%，12%，13%，16%，45%。請問以下哪個選項是字符 a, b, c, d, e, f分別對應的一組哈夫曼編碼？( )

A. 1111，1110，101，100，110，0

B. 1010，1001，1000，011，010，00

C. 000，001，010，011，10，11

D. 1010，1011，110，111，00，01

【答案】A

【考點】哈夫曼編碼/霍夫曼編碼

【解析】記住要點: 霍夫曼編碼左 0 右 1，哈夫曼編碼的形態不唯一，但是 WPL 一定是唯一的，哈夫曼樹的形態如下:

哈夫曼樹的形態不唯一，但是結點到根節點的路徑的長度一定是唯一的，路徑的長度是唯一的所以 WPL 是唯一，備考北化刷王道數據結構以前刷到過類似的題目hhh。合并的策略一定是選擇 n 個結點中最小的兩個結點進行合并，然后再將合并的結果放入合并的集合中。B、C、D 選可以從路徑上排除，這個題比較好 。

11. 給定一棵二叉樹，其前序遍歷結果為：ABDECFG，中序遍歷結果為：DEBACFG。請問這棵樹的正確后序遍歷結果是什么？( )

A. EDBGFCA

B. EDGBFCA

C. DEBGFCA

D. DBEGFCA

【答案】A

【考點】樹的遍歷

【解析】前序遍歷順序: 根左右 中序遍歷順序: 左根右

后序遍歷: 左右根 ==> EDBGFCA。

12. 考慮一個有向無環圖，該圖包括4條有向邊：(1,2)，(1,3)，(2,4)，和(3,4)。以下哪個選項是這個有向無環圖的一個有效的拓撲排序？( )

A. 4，2，3，1

B. 1，2，3，4

C. 1，2，4，3

D. 2，1，3，4

【答案】B

【考點】拓撲排序、有向圖

【解析】有向圖如下所示

拓撲排序: 度為 0 的點從圖中去掉。率先去掉 1 號點，(1,2)，(1,3) 這兩條邊去掉，度為 0 的點是 2 和 3，可以是 2 這個點先去掉，也可以是 3 這個點去掉，最后去掉 4 這個點，所以拓撲序列是: 1, 2, 3, 4 或者 1, 3, 2, 4。

13. 在計算機中，以下哪個選項描述的數據存儲容量最?。? )

A. 字節（byte）

B. 比特（bit）

C. 字（word）

D. 千字節（kilobyte）

【答案】B

【考點】數據存儲

【解析】數據存儲的基本單位: 字節(Byte)，數據的最小存儲單元: 比特(bit)。

1 Byte = 8 bit。

14. 一個班級有10個男生和12個女生。如果要選出一個3人的小組，并且小組中必須至少包含1個女生，那么有多少種可能的組合？（ )

A. 1420

B. 1770

C. 1540

D. 2200

【答案】A

【考點】排列組合

【解析】

① 一個女生，2 個男生

② 兩個女生，1 個男生

③ 三個女生

最終方案數: 540 + 660 + 220 = 1420。

15. 以下哪個不是操作系統？( )

A. Linux

B. Windows

C. Android

D. HTML

【答案】D

【考點】操作系統

【解析】HTML 前端三劍客之一，超文本標記語言。

第二部分 程序閱讀

程序閱讀

程序閱讀 ①

01 #include<iostream>
02 #include<cmath>
03 using namespace std;
04 
05 double f(double a,double b,double c){
06     double s=(a+b+c)/2;
07     return sqrt(s*(s-a)*(s-b)*(s-c));
08 }
09
10 int main(){
11    cout.flags(ios::fixed);
12    cout.precision(4);
13    
14    int a,b,c;
15    cin>>a>>b>>c;
16    cout<<f(a,b,c)<<endl;
17    return 0;
18 }

假設輸入的所有數都為不超過1000的正整數，完成下面的判斷題和單選題：

16. （2分）當輸入為“2 2 2”時，輸出為“1.7321”( )

【答案】?

【解析】a = 2, b = 2, c = 2, s = 3, 計算結果如下

17. （2分）將第7行中的"（s-b）*（s-c）"改為"（s-c）*（s-b）"不會影響程序運行的結果( )

【答案】?

【解析】乘法交換率 = a*b = b*a，所以交換后結果并不會發送變化。

18. （2分）程序總是輸出四位小數( )

【答案】?

【解析】cou.precision(4): 保留四位小數輸出。

19. （3分）當輸入為“3 4 5”時，輸出為( )

A. 6.0000

B. 12.0000

C. 24.0000

D. 30.0000

【答案】A

【解析】a = 3, b = 4, c = 5, s = 6，根據海倫－秦九韶公式知代碼求三角形面積，根據 a, b, c 的關系得知是直角三角形，所以面積為 6，故選 A。

20. （3分）當輸入為“5 12 13”時，輸出為( )

A. 24.0000

B. 30.0000

C. 60.0000

D. 120.0000

【答案】B

【解析】a = 5, b = 12, c = 13，根據海倫－秦九韶公式知代碼求三角形面積，根據 a, b, c 的關系得知是直角三角形，所以面積為 30，故選 B。

點評: 第一道題送分題 12 分應該拿滿分，語法簡單題，未拿到滿分的同學應該好好進行自我反思為什么語法難度的閱讀題會丟分。

程序閱讀 ②

01 #include<iostream>
02 #include<vector>
03 #include<algorithm>
04 using namespace std;
05 
06 int f(string x,string y){
07     int m=x.size();
08     int n=y.size();
09     vector<vector<int>>v(m+1,vector<int>(n+1,0));
10     for(int i=1;i<=m;i++){
11         for(int j=1;j<=n;j++){
12             if(x[i-1]==y[j-1]){
13                 v[i][j]=v[i-1][j-1]+1;
14             }else{
15                 v[i][j]=max(v[i-1][j],v[i][j-1]);
16             }
17         }
18     }
19     return v[m][n];
20 }
21
22 bool g(string x,string y){
23     if(x.size() != y.size()){
24         return false;
25     }
26     return f(x+x,y)==y.size();
27 }
28
29 int main(){
30     string x,y;
31     cin>>x>>y;
32     cout<<g(x,y)<<endl;
33     return 0;
34 }

21. （1.5分）f函數的返回值小于等于min（n,m）。( )

【答案】?

【解析】f 函數是一個典型的最長公共子序列模型，屬于動態規劃里面的內容

v[i][j]: 表示字符串 1 前 i 個字符和字符串 2 前 j 個字符，屬性值表示共有的子序列，狀態轉移方程如下

所以 f 函數最終的返回值應該小于等于兩個字符串中最小的那個長度。

22. （1.5分） f函數的返回值等于兩個輸入字符串的最長公共子串的長度。( )

【答案】?

【解析】子串: 要求連續; 子序列: 要求不連續，f 函數求的是最長公共子序列。

23. （1.5分）當輸入兩個完全相同的字符串時，g函數的返回值總是true( )

【答案】?

【解析】f 函數的返回值是字符串的長度，所以 f(x+x, y) = y.size() 是恒成立，所以 g 函數的返回值總是 true。

24. （3分）將第19行中的“v[m][n]”替換為“v[n][m]”，那么該程序( )

A. 行為不變

B. 只會改變輸出

C. 一定非正常退出

D. 可能非正常退出

【答案】D

【解析】當字符串 x 和 字符串 y 長度相等的情況情況不變，所以排除 B 和 C，當字符串 x 的長度大于或者小于字符串長度 y 導致數組越界訪問，可能導致程序異常終止。

25. （3分）當輸入為“csp-j p-jcs”時，輸出為: ( )

A. 0

B. 1

C. T

D. F

【答案】B

【解析】csp-jcsp-j p-jcs，f 函數的返回值是 5，和 p-jcs 長度相等，g 函數返回 true，bool 類型的輸出 true 自動轉化成 1。

26. （3分）當輸入為“csppsc spsccp”時，輸出為: ( )

A. T

B. F

C. 0

D. 1

【答案】D

【解析】csppsccsppsc spsccp，f 函數的返回值是 6，和 spsccp 長度相等，g 函數返回 true，bool 類型的輸出 true 自動轉化成 1。

點評: 第二道題 f 函數考察同學們對于動態規劃學習的檢驗。

程序閱讀 ③

01 #include <iostream>
02 #include <cmath>
03 using namespace std;
04 
05 int solve1(int n){
06     return n*n;
07 }
08
09 int solve2(int n){
10    int sum=0;
11    for(int i=1;i<=sqrt(n);i++){
12         if(n%i==0){
13             if(n/i==i){
14                 sum+=i*i;
15             }else{
16                 sum+=i*i+(n/i)*(n/i);
17             }
18         }
19     }
20     return sum;
21 }
22
23 int main(){
24     int n;
25     cin>>n;
26     cout<<solve2(solve1(n))<<" "<<solve1((solve2(n)))<<endl;
27     return 0;
28 }

27. （1.5分）如果輸入的n為正整數，solve2函數的作用是計算n所有的因子的平方和 ( )

【答案】?

【解析】solve2 函數代碼解析如下:

28. （1.5分） 第13~14行的作用是避免n的平方根因子i（或n/i）進入第16行而被計算兩次 ( )

【答案】?

【解析】平方數 n 中出現 i 是 n 的因子時，必然 n/i 和 i 相同，同一個因子出現兩次但是計算只計算一次，所以該判斷題敘述正確。

29. （1.5分）如果輸入的n為質數，solve2（n）的返回值為n2+1 ( )

【答案】?

【解析】循環枚舉 i 是從 1 開始枚舉，質數的定義除了 1 和它本身外沒有其余的因子，所以 sum = n*n + 1*1，所以敘述正確。

30. （4分）如果輸入的n為質數 p 的平方，那么 solve2（n）的返回值為( )

A. p2+p+1

B. n2+n+1

C. n2+1

D. P4+2p2+1

【答案】B

【解析】n 的因子有 1, p, n，sum 統計的是 n*n + p*p + 1*1，題目說 n 是質數 p 的平方，那么 p*p = n，等價替換返回值等于 n*n + n + 1 或者 p*p*p*p + p*p + 1，兩個答案的變形都算正確，所以最終選 B。

31. （3分）當輸入為正整數時，第一項減去第二項的差值一定 ( )

A. 大于0

B. 大于等于0且不一定大于0

C. 小于0

D. 小于等于0且不一定小于0

【答案】D

【解析】特殊代值法排除，當 n 為 1 時 solve2(solve1(n))-solve1((solve2(n)))結果都為 0，因為模擬計算后發現都為 1，所以排除 A、C 兩個選項；代入一個值 n為 3 的情況，solve1(3) = 9，solve2(9) = 1*1 + 9*9 + 3*3 = 91，solve2(3) = 1*1 + 3*3 = 10，solve1(10) = 100，91 - 100 = -9，所以選 D，暑期集訓說過這種結論題一般代值大概率能找出正確答案，算是做題技巧。

32. （3分） 當輸入為“5”時，輸出為 ( )

A. 651 625

B. 650 729

C. 651 676

D. 652 625

【答案】C

【解析】solve1(5) = 25，solve2(25) = 1*1 + 5*5 + 25*25 = 651。

solve2(5) = 1*1 + 5*5 = 26，solve1(26) = 26*26 = 676。

點評: 數學知識因數分解。

第三部分 程序完善

程序完善

(1)(尋找被移除的元素)問題:原有長度為 n+1 公差為 1 等升數列，將數列輸到程序的數組時移除了一個元素，導致長度為 n 的開序數組可能不再連續，除非被移除的是第一個或最后之個元素。需要在數組不連續時，找出被移除的元素。試補全程序。

01 #include <iostream>
02 #include <vector>
03 
04 using namespace std;
05 
06 int find missing(vector<int>& nums){
07    int left = 0, right = nums.size() - 1;
08    while (left < right){
09        int mid = left + (right  left) / 2;
10        if (nums[mid] = mid + ①){
11            ②;
12        }else{
13            ③
14        }
15    }
16    return ④;
17 }
18 
19 int main(){
20     int n;
21     cin >> n;
22     vector<int> nums(n);
23     for (int i= 0; i< n; i++) cin >> nums[i];
24     int missing_number = find_missing(nums);
25     if_(missing_number == ⑤) {
26         cout << "Sequence is consecutive" << endl;
27     }else{
28         cout << "Missing number is " << ,missing numbeer << endl;
29     }
30     return 0;
31 }

二分適用條件: ① 區間單調性 ② 二分的答案滿足單調性

單調遞增區間查找 >= x 的最小值

int Find_L(int n, int num){ // n 表示 n 個數, num 查詢的數 
    int L = 0, R = n-1; // L:左端點, R:右端點 
    while(L < R){
        int mid = (L+R)>>1; //中間點 
        if(a[mid] >= num) R = mid; //左子區間 
        else L = mid + 1; //右子區間 
    }
    return L; //二分的 >= num 的最小值 
}

單調遞增區間查找 <= x 的最大值

int Find_R(int n, int num){ //n:n個元素,num:查詢值 
    int L = 0, R = n - 1; //L:左端點 R:右端點 
    while(L < R){ 
        int mid = (L + R + 1)/2; //中間點 
        if(a[mid] <= num) L = mid; //右區間 
        else R = mid - 1; //左區間 
    }
    return R; // 二分 <= num 的最大值 
}

33. ① 處應填( )

A. 1

B. nums[0]

C. right

D. left

【答案】B

【解析】等差數列公差 1 說明原序列具有連續性，連續必然滿足 nums[0] + mid == nums[mid]，不連續 nums[mid] 必然大于 nums[0] + mid。

34. ②處應填( )

A. left=mid+1

B. right=mid-1

C. right=mid

D. left=mid

【答案】A

【解析】當 if 成立說明左區間連續，答案必然在右區間 [mid+1, right] ，通過不斷調整左指針 left 和右指針 right 來確定答案處于哪個區間，因此需要將 left 修改成 mid+1。

35. ③處應填( )

A. left=mid+1

B. right=mid-1

C. right=mid

D. left=mid

【答案】C

【解析】if 不成立答案處于左區間 [left, mid]，只需要修改指針 right = mid。

36. ④處應填( )

A. left+nums[0]

B. right+nums[0]

C. mid+nums[0

D. right+1

【答案】A

【解析】返回的是被刪除的數，被刪除的數即不連續的位置 + 起始值。

37. ⑤處應填( )

A. nums[0]+n

B. nums[0]+n-1

C. nums[0]+n+1

D. nums[n-1]

【答案】D

【解析】如果 n 個數連續， left = right = n-1，返回的數必然是序列中的最后一個數，反之則返回的數即是被刪除的數。

這個題大多數認真學的同學都是滿分，注意認真學并不是說上課聽講，而是自己課后自己動手去模擬過二分的過程，聽老師講懂了和自己動手驗證老師上課講的內容記憶會更加深刻。

②(編輯距離) 給定兩個字符串，每次操作可以選擇刪除 (Delete)、插入 (Insert)、替換 (Replace)，一個字符，求將第一個字符串轉換為第二個字符串所需要的最少操作次數。

1.#include <iostream>
2.#include <string>
3.#include <vector>
4.using namespace std;
5. 
6.int min(int x,int y,int z){
7.    return min(min(x,y),z);
8.}
9. 
10.int edit_dist_dp(string str1,string str2){
11.    int m=str1.length();
12.    int n=str2.length();
13.    vector<vector<int>> dp(m+1,vector<int>(n+1));
14. 
15.    for(int i=0;i<=m;i++){
16.        for(int j=0;j<=n;j++){
17.            if(i==0)
18.                dp[i][j]= ①;
19.            else if(j==0)
20.                dp[i][j]= ②;
21.            else if(③)
22.                dp[i][j]= ④;
23.            else
24.                dp[i][j]=1+min(dp[i][j-1],min(dp[i-1][j],⑤)); 
25.        }
26.    }
27.    return dp[m][n];
28.}
29. 
30.int main(){
31.    string str1,str2;
32.    cin>>str1>>str2;
33.    cout<<"Mininum number of operation:"
34.    <<edit_dist_dp(str1,str2)<<endl;
35.    return 0; 
36.}

一、狀態表示：dp[i][j]

1. 集合：將 str1[1~i] 和 str2[1~j] 匹配的操作數量的集合

2. 屬性：最少操作次數

二、狀態計算：

1. 思想-----集合的劃分

2. 集合劃分依據：根據最后一步進行劃分

刪除操作：dp[i][0] = i;

插入操作：dp[0][i] = i;

3. 具體劃分為3類：

1. 增加：dp[i][j] = dp[i, j - 1] + 1

2. 刪除：dp[i][j] = dp[i - 1, j] + 1

3. 修改：dp[i][j] = dp[i - 1, j - 1] + 1 (str1[i] != str2[j])

4. 匹配：dp[i][j] = dp[i - 1][j - 1] (str1[i] == str2[j])

38. ① 處應填( )

A. j

B. i

C. m

D. n

【答案】A

【解析】第一個字符串長度為 0，第二個字符串長度為 j，將第一個字符串轉換成第二個字符串操作的次數是 j，這個操作是增加。

39. ② 處應填( )

A. j

B. i

C. m

D. n

【答案】B

【解析】第一個字符串長度為 i，第二個字符串長度為 0，將第一個字符串轉換成第二個字符串操作的次數是 i，這個是刪除操作。

40. ③處應填( )

A. str1[i-1]==str2[j-1]

B. str1[i]==str2[j]

C. str1[i-1]!=str2[j-1]

D. str1[i]!=str2[j]

【答案】A

【解析】匹配操作，第一個字符串和第二個字符串匹配。

41. ④處應填( )

A. dp[i-1][j-1]+1

B. dp[i-1][j-1]

C. dp[i-1][j]

D. dp[i][j-1]

【答案】B

【解析】匹配的情況不需要操作

42. ⑤處應填( )

A. dp[i][j] + 1

B. dp[i-1][j-1]+1

C. dp[i-1][j-1]

D. dp[i][j]

【答案】C

【解析】前 i-1 個字符與前 j 個字符最少操作次數、前 i 個字符與前 j-1 個字符最少操作次數、前 i-1 個字符與前 j-1 個字符最少操作三者取 min 后 + 1。

第四部分 總結

關于孩子是否適合走信奧這條路我的觀念依舊是能從中學到什么，對以后的學習生活有什么幫助，如果太看中成績，那么 99.9999% 的學生都是失敗者。

言歸正傳說一下考試試卷考點分析：

暑期集訓的內容沒有花太多的時間講動態規劃，因為想的是不太好挖空，主要太簡單，沒想到今年的題型比去年的簡單，對于系統學習的同學大部分都是 90 左右，這里的系統學習不是說考試出現的概率小就不考的誤區，程序閱讀沒學過動態規劃影響不大，暑期初賽集訓課后有認真思考的同學 65 左右。

學習建議:

① 戒驕戒躁，靜心學習

② 按照要求課后自覺上機練習(考場兩小時，課后兩三年功夫)

③ 戒掉功利主義的心態，如果只是為了保送清華北大建議放棄，打信奧能進清北，全力沖刺高考文化課妥妥也牛掰(破音)

④ 不要相信不勞而獲，很多宣傳主打一個就是夸張宣傳，比如跟著誰學零基礎包 CSP-J 獲獎(主打吹牛)、包 CSP-J 晉級(主打考級)

⑤ 系統學習

⑥ 職業規劃，未來規劃專業不讀計算機、不讀研、不選擇和互聯網相關行業打不打信奧都沒有什么關系

教學反思:

① 不講概率事件，也不會按著家長的要求去講機構的內容，不會再將整個競賽體系打亂，union 是 2023 新大綱的內容，認為考是一個小概率事件，但是確實是考了，動態規劃程序題小概率事件考了

② 將競賽體系進行順序的調整，考核不通過的學員不會講下一個階段的內容

③ 第一年參賽只能說去和已經獲獎的對手同臺競技，第一次比賽結束后續一定要好好學習，課后認真刷題(杜絕水題)

④ 和機構博弈的學員不帶，就是機構不開課，家長就說自己找了教練，教務必然會各種挽留家長(已經遇到過幾次，心累，沒有那個功夫和機構斗嘴皮子，您說的全對！每天笑哈哈，拒絕精神內耗)

⑤ 要想出成績不會再順著學員的心態數據削弱，完全掌握就是完全掌握，有些細節不注意錯就是錯，有則改之，無責加勉勵

、BeautifulSoup簡介

BeautifulSoup是Python爬蟲應用解析Html的利器，是Python三方模塊bs4中提供的進行HTML解析的類，可以認為是一個HTML解析工具箱，對HTML報文中的標簽具有比較好的容錯識別功能。lxml是一款html文本解析器，BeautifulSoup構建對象時需要指定HTML解析器，推薦使用lxml。

BeautifulSoup和lxml安裝命令：

1.pip install -i https://pypi.tuna.tsinghua.edu.cn/simple bs4

2.pip install -i https://pypi.tuna.tsinghua.edu.cn/simple lxml

加載BeautifulSoup：

1.from bs4 import BeautifulSoup

BeatifulSoap解析HTML報文的常用功能：

1. 通過BeautifulSoup對象可以訪問標簽對應的html元素、并進一步訪問標簽的名字、屬性、html元素標簽對中的內容。
   案例：from bs4 import BeautifulSoup
2. import urllib.request
3. def getURLinf(url):
4. header = {'User-Agent': 'Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/44.0.2403.157 Safari/537.36'}
5. req = urllib.request.Request(url=url,headers=header)
6. resp = urllib.request.urlopen(req,timeout=5)
7. html = resp.read().decode()
8. 
   
9. soup = BeautifulSoup(html,'lxml')
10. return (soup,req,resp)
11. 
    
12. soup,req ,resp = getURLinf
13. print(soup.p)
14. print(soup.link)
15. print(soup.title)
16. print(soup.link.attrs)
17. print(soup.link['rel'])

通過標簽的contents屬性，可以訪問其下嵌套的所有下級HTML元素，這些該標簽下的子標簽對應的HTML元素放到一個contents 指向的列表中。

如：print(soup.body.contents)

可以訪問標簽對應的父、子、兄弟及祖先標簽信息；

使用strings屬性迭代訪問除標簽外的所有內容；

可以使用find、find_all、find_parent、find_parents等系列方法查找滿足特定條件的標簽；

使用select通過css選擇器定位特定標簽。

二、一些解析技巧

在HTML解析時，如果通過簡單的tag、或單個tag屬性（如id、class）或文本一次搜索或select定位是最簡單的，而有些情況需要使用組合方法才能處理。

2.1、通過標簽的多個屬性組合定位或查找

經常有些要定位的標簽有很多，按單個屬性查找也有很多，得使用多個屬性查找。如：

上面的html文本中有多個id為article_content的div標簽，如果使用：

1. >>> text="""```html
2. <div id="article_content" class="article_content clearfix">
3. ......
4. </div>
5. <div id="article_content" class="article_view">
6. ......
7. </div>
8. <div id="article_view" class="article_view">
9. ......
10. </div>"""
11. >>> s = BeautifulSoup(text,'lxml')
12. >>> s.select('div#article_content')
13. [<div class="article_content clearfix" id="article_content">......</div>,
14. <div class="article_view" id="article_content">......</div>]
15. >>>

就會返回兩條記錄。這時候就可以使用多標簽屬性定位的如下4種語句：

1. >>>s.select('div#article_content[class="article_content clearfix"]')
2. [<div class="article_content clearfix" id="article_content">......</div>]
3. >>>s.select('div[id="article_content"][class="article_content clearfix"]')
4. [<div class="article_content clearfix" id="article_content">......</div>]
5. >>>s.find_all("div",id="article_content",class_='article_content clearfix')
6. [<div class="article_content clearfix" id="article_content">......</div>]
7. >>>s.find_all("div","#article_content",class_='article_content clearfix')
8. [<div class="article_content clearfix" id="article_content">......</div>]

以上四種方式是等價的，因為id可以用#來標記，class在查找時需要和Python關鍵字class區分，因此有上述不同方法，注意select的每個屬性必須用中括號括起來，不同屬性的中括號之間不能有空格，如果有空格表示的就不是查找同一標簽的屬性，空格后的屬性表示前一個屬性對應標簽的子孫標簽的屬性。

2.2、利用tag標簽關系定位內容

tag標簽關系包括父子、兄弟、祖先等關系，有時要查找或定位的內容本身不是很好定位，但結合其他標簽關系（主要是父子、祖先關系）則可以唯一確認。

案例：

這是博文中關于博主個人信息的部分報文：

1. <div class="data-info d-flex item-tiling">
2. <dl class="text-center" title="1055">
3. <a href=" " data-report-click='{"mod":"1598321000_001","spm":"1001.2101.3001.4310"}' data-report-query="t=1">
4. <dt><span class="count">1055</span></dt>
5. <dd class="font">原創</dd>
6. </a>
7. </dl>
8. <dl class="text-center" data-report-click='{"mod":"1598321000_002","spm":"1001.2101.3001.4311"}' title="22">
9. <a href=" " target="_blank">
10. <dt><span class="count">22</span></dt>
11. <dd class="font">周排名</dd>
12. </a>
13. </dl>
14. </div>

以上報文中，如果要取博主的原創文章數和周排名，原創文章數和博主周排名的tag標簽完全相同，二者都在span標簽內，標簽的屬性及值都相同，只是span標簽的父標簽dt標簽的兄弟標簽dd標簽的string的中文內容才能區分。對于這種情況，首先要通過祖先標簽<div class="data-info d-flex item-tiling">定位到祖先標簽，再在祖先標簽內通過中文字符串定位到要訪問屬性的兄弟標簽的子標簽，然后通過該子標簽找到其父標簽的父標簽，再通過該父標簽的dt子標簽的span子標簽訪問具體取值。

示例代碼如下：

1. >>> text="""
2. <div class="data-info d-flex item-tiling">
3. <dl class="text-center" title="1055">
4. <a href=" " data-report-click='{"mod":"1598321000_001","spm":"1001.2101.3001.4310"}' data-report-query="t=1">
5. <dt><span class="count">1055</span></dt>
6. <dd class="font">原創</dd>
7. </a>
8. </dl>
9. <dl class="text-center" data-report-click='{"mod":"1598321000_002","spm":"1001.2101.3001.4311"}' title="22">
10. <a href=" " target="_blank">
11. <dt><span class="count">22</span></dt>
12. <dd class="font">周排名</dd>
13. </a>
14. </dl>
15. </div>"""
16. >>> s = BeautifulSoup(text,'lxml')
17. >>> subSoup = s.select('[class="data-info d-flex item-tiling"] [class="font"]')
18. >>> for item in subSoup:
19. parent = item.parent
20. if item.string=='原創':
21. orignalNum = int(parent.select('.count')[0].string)
22. elif item.string=='周排名':
23. weekRank = int(parent.select('.count')[0].string)
24. 
    
25. >>> print(orignalNum,weekRank)
26. 1055 22
27. >>>

注意：上面的select使用的也是標簽的屬性來定位標簽，并且兩個中括號之間有空格，表明后一個要查找的標簽在前一個屬性對應標簽的子孫標簽范圍內。

2.3、分析前去除程序代碼避免干擾

在解析HTML報文時，絕大多數情況是需要分析有用的標簽信息，但作為技術文章，大部分的博文中都有代碼，這些代碼可能會對分析進行干擾。如本文中的代碼含有一些分析的HTML報文，如果獲取本文的完整HTML內容，這些報文在非代碼部分也會出現，此時要排除代碼的影響，可以將代碼先從分析內容中去除再來分析。

目前大多數技術平臺的博文編輯器都支持對代碼的標識，象markdown等編輯器代碼的標簽為code標檢，如果有其他編輯器用不同標簽的，只有確認了標簽名，都可以按下面介紹的類似方式來處理。

處理步驟如下：

獲取報文；

構建BeatifulSoap對象soup；

通過soup.code.extract()或soup.code.decompose（）方式就從soup對象中去除了代碼部分，decompose方法與extract方法的區別就是decompose直接刪除對應對象數據而extract再刪除時將刪除對象單獨返回。

三、小結

本文介紹了使用BeatifulSoap解析HTML報文的三個使用技巧，包括通過多屬性組合查找或定位標簽、通過結合多個標簽關系來定位標簽以及去除html報文中的代碼標簽來避免代碼對解析的影響。

寫字不易，敬請支持：

如果閱讀本文于您有所獲，敬請點贊、評論、收藏，謝謝大家的支持！

————————————————

版權聲明：本文為轉載文章，如有侵權，請聯系作者刪除。