2025學科校內賽心得

這次的校內賽是由明達學長出題的，總共六題，難度非常的高。

pA 華生的資料注入

我覺得這題可能有問題因此我選擇打好題敘。

題文

華生是一名時間旅者。為了避免未來L公司的人工智能「天眼」(SkyEyes)失控導致世界毀滅，她穿越回天眼仍在訓練階段的現在。今日，華生已經成功打入L公司內部，成為一名L公司高層。
已知要阻止天眼失控，其中一個條件是需在訓練階段加入夠多符合某些標準的特殊資料。華生自己還要處理太多其他導致天眼失控的因素，於是將產生這些資料交給自己的得意助手－－也就是你。
華生對於每筆資料會以 $S,m,M$ 紀錄，代表該筆資料應該符合以下所有條件：

• 總和等於 $S$。
• 最小值等於 $m$。
• 最大值等於 $M$。

輸入

輸入第一行包含一個整數 $t$。
接下來t行，每行包含整數 $S,m,M$。
$1\le t\le1000$
$0\le m \le M\le100$

輸出

輸出 $t$ 行，每行可包含最多 100 個整數，代表符合對應條件的資料。如果有多種符合條件的解，輸出任一個解即可。已知必有解。

e.g.

//input
2
15 1 5
16 0 9
//output
5 3 4 1 2
0 1 3 3 9

我在這題的實作上有許多問題，像是我對範測中輸出 “1 5 4 4 1\n0 1 3 3 9\n” 收到$WA$。
但是輸出 “5 3 4 1 2\n0 1 3 3 9\n” 卻是$AC$。
非常的玄，我嚴重懷疑 spj 有問題，但 kzzz 神奇的AC了。

pB 彭羅的宇宙棋盤

題文

給一個 $n\times m(1\le n, m \le 10^5)$ 的圖，在圖上一次只能往右或往下移動一個，圖上有 $k(0\le k \le max(mn, 2000)) $個無法通過的點，問從 $(0, 0)$ 出發到 $(n-1, m-1)$ 的方法數 $%10^9+7$。
subtask 1 30% $1\le n, m \le 2000$。
subtask 2 70% 無限制。

這題我的想法是 DP 蓋圖拿子題，有試使用 C++ vector 蓋 $nm$ 的圖，但一樣只有 $30%$，由於是用 0j，有人用 python 蓋 $nm$ 拿了 80%，相當破防。
賽後發現可以用排容處理 $k$，而且好像是 CSES addional-problems 的題目。

pC 貝兒的分類器

閱讀測驗題，我沒看(0%)，kzzz說超裸，讀完就有。

pD 約瑟夫的遞增輪盤

約瑟夫問題，$N$ 個人，數到 $k$ 的人淘汰，$k$ 會動態調整: $k=1+ai+b(1\le a, b\le2\times 10^5,i為淘汰的人數)$，求最後存活的人的編號。

subtask 1 10% $a=0$
subtask 2 20% $N\le 2000$
subtask 3 10% 無限制。

這題 kzzz 直接砸pbds order set。我只有拿子題20%。

pE 泰拉的地形改造

$N\times M(1\le N, M\le 200)$的表格，只會有3種字符 0,+,-，每次可以選一行或列+/-1，讓最後0的位置是0，+的位置>0，-的位置<0，求最小操作次數，無解輸出-1。

subtask 1 30% $N, M\le4$
subtask 2 70% 無限制。

相當難的題目，但我猜是 DP 或是神奇的枚舉剪枝，但我不會，好像輸出-1拿了20%。

pF 桑義的完美陣列

給一個陣列 $A$ 有 $N(1\le N\le 2\times 10^5)$ 個元素$\forall 1\le i \le N(1\le a_i\le10^9)$，，求最少要刪除幾個元素使甚下的每個元素都互質。
我在賽中就想到了蓋到$2 \times 10^5$ 的質數前綴和，但記憶體卡很死，最後有成功使它到$2 \times 10^5$，但是還是$WA$ 90%。

結語

我很不滿意我這次的成績(160%)，就算加上 pA 和 pC，也只有360%，嚴重小於 kzzz 的 470%。