Part 1 題目列表

• P7075 [CSP - S2020] 儒略日
• P7076 [CSP - S2020] 動物園
• P7077 [CSP - S2020] 函數調用
• P7078 [CSP - S2020] 貪吃蛇

Part 2 考試時間線

8:02 開題， 僅僅讀了 10 分鐘 T1 題目，就得出結論，大模擬。

9:20 在與 T1 長達 ···（數不過來了） 的搏斗后，成功過了大樣例，快速開 T2。

9:50 十分鐘看題，十分鐘寫題，十分鐘調題（算多了一點），一遍過大樣例。

11:00 當時一看，這不明顯的數據結構大水題嗎（看看我那驚人的判斷力），最終沒調出來。

11:20 只好寫了一個超級大暴力。但當我把視野望向那仿佛遙不可及的 T4 時，卻發現這不是 貪吃蛇 嗎，我以前可是做過的，但是沒調出來。

12:00 結束，開始擔心未刪調試。

Part 3 題目分析

T1

都說了是 超級打分討，當然要加一點二分。

錯因：

有一個 1582 寫成了 1982

T2

最簡單的一道，就不再多說了，要注意的是，答案最大值為：

開 unsigned long long 都會爆。

所以要特判。

T3

考完后成功發現時間復雜度是偽的。

首先這怎么看都像是一個圖論，因為通過函數的調用關系，可以很輕松的建立一個 DAG 出來

比如這組數據：

【輸入】

1
0
5
1 1 1
2 2
2 4
3 2 1 2
3 2 1 3
2
4 5

【輸出】

12

可以建出如下圖：

這里補了一個 0 號節點作為主函數，相當于只是調用一個主函數

首先我們發現：

所以我們只需要分別知道原數組乘的倍數，和每一個加數乘的倍數即可。

第一個十分簡單，一個反向建邊，加一個拓撲即可。

而第二個有一點需要注意，我們要反向枚舉邊，因為是后面的影響前面的。

T4

這里做一個分類討論：

• 最大的蛇吃了最小的蛇不是最小的蛇

  【策略】

  應當吃掉，如何都不虧（證明略）

• 最大的蛇吃了最小的蛇是最小的蛇

  【策略】

  最開始我們頭腦簡單的認為這當然不能吃，因為吃了自己下一輪也得死，但是當我們再往下面枚舉一層：

  1. 下一輪最大的蛇吃了自己不是最小的蛇

     因為這條蛇會選擇吃你，因而你在這一輪不能吃

  2. 下一輪最大的蛇吃了自己是最小的蛇

     這里又要看下下一輪的蛇

我們發現這是一個遞歸的過程，一但要考慮第二種情況就會遞歸到：

1. 蛇的數量為 2
2. 這條遞歸到的蛇吃了后不是最小的蛇

且滿足：

• 上個蛇要吃則這一個蛇不吃
• 上一個蛇不吃則這一個蛇吃

（滿足奇偶性）

Part 4 總結

總分：70 + 95 + 45 + 20 = 230

預期得分： 100+100+45+20=265

改進方案：

• 在檢查時檢查一些特殊情況
• 當發現不能在短時間內找到正解的話，先保證打滿部分分
• 節約時間