# 命題歷程總覽

> 作者：沈宗叡（暴力又被TLE）
> 滅台率：$8/14$（持續更新中）

## 前言

「APCS 模擬測驗團隊」是一個由國小、中學、大學生組成的社群，每個月最後一個禮拜六的晚上會舉辦 APCS 模擬測驗。而我在第十次模擬測驗的準備期間加入出題組，命題旅程，啟動！

## 心得

原本以為會寫題，理應就會出題。然而出題不是 `compile(random("idea"))`，而是 `assert self`，我不僅僅要寫出嚴絲合縫的權威官解，還要模擬數十種寫錯的我，然後用 Generator 讓這些我 TLE、WA、RE 到懷疑人生。

對我來說，出題的難點根本不在「出題」，而在於寫一個足夠好的 Generator，要絞盡腦汁預判不會正解的參賽者可能用甚麼方法唬爛、會正解的參賽者又有可能在哪個地方粗心而漏掉 edge case、不會閱讀的參賽者又可能漏看哪個條件而寫出假解——這些我都得先「試跌」過一輪，才能有效預判他們摔倒的英姿。寫 Generator 的重點不在於 AC，而是先嘗試寫出 WA 或 TLE 卻很有機會 AC 的假解，再想辦法致其於死地。這簡直不只是在寫題、出題，而是在布置一個大型犯罪現場，假解是被害者、強度爆表的測資是凶器、Generator 是決定性證物，而我就是那個精心布局的完美主義變態殺手。從前我總怕被兇手幹掉，而如今我了解到，兇手在爆砍別人之前難免需要先在自己身上刺幾刀，測試這把刀能有多鋒利。

我不再只是單純地想著出題，而是從最生活化的小問題出發，腦力激盪出考點多元、題述放飛思考的題目，想著讓會寫的人享受、讓不會寫的人崩潰、讓懂梗的人會心一笑。出題不只是 `compile(random("idea"))`，而是 `assert self`，最終 `push` 一份自己真心滿意、誠心相信的作品。

就算沒人 AC 也無妨，我已不只 AC，也 TLE、WA、RE 了自己。

## 初見滅台：[大智慧學苑的朋友圈](https://hackmd.io/@apcs-simulation-/B14TCOt0C)

最一開始加入出題組大概是 2024/10 初，原本想說先觀摩一下其他人出題的大致流程，結果第一場直接上了ww。

當時特別喜歡 DSU 這個資料結構，所以就出了一題可以用 DSU 也可以用 BFS/DFS 解的題目：

> 在一個 $r \times c$ 的二維平面上，有 $n$ 個點與 $m$ 條邊，每條邊紀錄兩個點之間的相對位置（$\Delta x, \Delta y$），每一個連通塊都必定有點在二維平面的邊緣上。輸出整個二維平面並標示出所有點。

但這樣 $r \times c$ 就不能太大，為了考離散化增加實作難度，所以我稍微修改：

> 每個點有獨特 $value$，而**左右相鄰**且 $value$ 差值 $\le$ 常數 $k$ 的點，兩者所屬的連通塊會 merge。最終輸出連通塊數量、最大連通塊大小。

只有相鄰的會 merge 就能達成原題找出絕對位置的需求、限定左右相鄰就能確定他的 $x, y$ 沒有搞混。

為了進一步確保沒有將座標旋轉、翻轉：

> 還要輸出離原點的曼哈頓距離最小的點，相同則取 $y$ 小的。

這樣基本上就能完全確認絕對位置正確了，而且座標離散、相對位置轉絕對位置也沒有很好實作、還要處理後續的 merge，這個題目十分有實作挑戰性。

但更有挑戰性的不是寫出 AC 解而是寫出 Generator。

畢竟是第一次寫 Generator，基本上就是亂糊，可讀性極低。為了確保我能卡到我想卡的東西，我將 AC 解複製多份，並修改一些容易錯的地方（$x, y$ 搞反、曼哈頓距離相同時取成 $x$ 小的、$\Delta x, \Delta y$ 方向搞反、在邊緣對齊時的各種 edge case、不只左右連上下也 merge...），生完一份測資後再跑一次所有這些假解確保他們會 WA。還有完全圖、遞迴深度會很深之類的特殊圖。

生成所有點的絕對座標時，為了確保每個連通塊都至少有點在四個邊緣上，我也是用了超級噁心的寫法，現在看真的不忍直視，總之這個 Generator 充滿了無數可以吐槽的地方。

最瞎的是，我為了讓點不要在同一個位置而把他們丟進 `set` 去重，但最後 `n` 卻是原來隨機生成的，沒有重新 `n = len(set)`，所以我生出來的測資甚至爛了 $4$ 筆，賽後被參賽者指正後才重新修改（並人工 rejudge）。

最終這實作難題成功滅台（無人 AC），我記得最高拿 $40$ 分。

但官解只有區區 $60$ 幾行，所以絕對是參賽者的問題（哼！）。

（順帶一提，我當時很喜歡寫 iterative DSU，但我現在發現 recursive 更快 QAQ）

## 滅台之咒：[太簡單的石板](https://hackmd.io/@apcs-simulation-/SkH6915l1e)

時至今日這題仍是我出過最難的一題。

最一開始是在數學排列組合單元看到一個題目：

> 給一個 $2 \times 5$ 的方格，有多少種方法可以將 $1 \sim 10$ 填入，並使數字每一行列由左到右、由上到下都遞增？

可以將題目轉化為走一個 $5 \times 5$ 的 $2$ 維方格，每次往右走就在 $2 \times 5$ 方格的上排填入一個數字，往上走則在下排填，並且**不能越過對角線**。

由此可看出這是一題 DP，$m \times n$ 的方格就要開 $n$ 維、$m \times m \times \dots \times m$ 的方格。
有趣的是在 $n = 2$ 時，答案就是「卡塔蘭數」，由走方格解法可知 $n = 2$ 時此題跟卡塔蘭數定義完全一致。因此我也叫這題「高維卡塔蘭數」。

我原本高一要寫關於這個的小論文，但在文獻探討的時候找到一篇論文寫了他的公式。所以就沒寫了。於是我把他出成模擬賽題目 :D。

> 給一個 $m \times n$ 方格，有多少種方法可以將 $1 \sim m \times n$ 填入，並使數字每一行列由左到右、由上到下都遞增？

結果被橘子（2024 IOI 國手）嗆：這是楊表裸題。

我去維基百科上查了楊表，確實如此。但要套公式的話還需要算階乘、階乘的乘法反元素等等，不是 APCS 範圍內的東西，但數學解的實作量之小實在太破壞平衡，而且當時適逢 AI 大軍大舉入侵競程圈，這題發給當時還有點笨笨的 ChatGPT 3.5 仍直接被破解，所以得加難：

> 其中 $k$ 個格子被封印不能填數字，改為填入 $1 \sim m \times n - k$。

這下公式解沒轍了，必須 DP，而且是多維 DP。

主要是正常和封印狀態之間該如何轉移有很大的問題，很難想出也很難證明。
總之直接去標題的連結看 AC code 吧，我也不會解釋了...

這題的 Generator 幾乎是純手生，而其中一個子題我甚至用所有的測資點把 Python 遞迴深度 $1000$ 的限制卡掉，因此 Python 的遞迴寫法會 RE 整個子題，必須要用 Stack 模擬遞迴，或者用 `sys.setrecursionlimit` 修改深度限制。

不負眾望地滅台，首殺甚至耗時 $970$ 小時 $30$ 分 $21$ 秒，難以突破的神話。

雖然這題本身很有趣，但作為 APCS 模擬賽的題目、甚至作為一題程式競賽的題目都有很多很大的問題，首先 AC code 不只難想，還難以證明正確性（我是窮舉小 case 並暴搜答案，確保與官解一致），實作難度也高，幾乎不可能在賽中、尤其是 APCS 的後測環境中寫出來並驗證。

因此，出自己「會寫且**會證**」的題是出題的基本門檻，這回我清晰地意識到這點。

## 超噁實作：[All I want for Minecraft is CRAFT](https://hackmd.io/@apcs-simulation-/ryY68_eB1x)

連續兩次 p3 滅台，不敢給我出 p3、p4 了，所以我來出 p2。（這是 12 月的題目，看這標題就很聖誕是吧？）

簡單來講就是題目巨長巨複雜的模擬題，要做二維陣列的旋轉、翻轉、擷取出有內容部分的矩形並枚舉所有範圍內的位移、形狀配對等等...還有很多很噁心的 edge case，要辨識出「執行失敗的操作」並跳過。Python AC 解 160 行左右，C++ 似乎是 300 行起跳。

經過我的實測大概 1 小時左右能生出完全解的初版，再 debug 一下期望上一個半小時就能解決，但我太天真了。但又說那次模擬賽的其他題目實作難度非常低，p4 我也 10~15 分鐘想出詳細解法，20~30 分鐘內 AC。而且我給的子題說實話很單純，完全是**普通** p2 的實作難度（自己吐槽），因此我個人感性認為就算很不幸滅了，應該至少有人拿得到子題分。
結果仍不負眾望滅台，而且**沒有任何人**拿到**任何分數**。大部分人看到超長題敘就被勸退了，最終只有一個人在認真寫，但寫了 300 多行以後還是沒寫出來，整場只寫了這題，值得立碑紀念的勇士啊！

先說這次的 Generator 真的很難寫，畢竟是大實作題，而且操作都很瑣碎，所以從「想出一個好的生成邏輯」我就卡了挺久。最終 Generator 洋洋灑灑寫了 400 多行，總共花了半個禮拜，在模擬賽前一兩天才生出來。值得一提的是，這次是我開始將 Generator 的各部分模組化，將 Generator 的大架構嘗試拆分成通用的函式，這樣以後出題就只需要寫實際生成測資的部分就好了，但整體架構仍然偏陽春就是了。

這題除了實作量過大這最主要的問題，輸入格式數字、字元兩種型態混雜，導致 C 和 C++ 使用者比較難處理輸入，造成語言之間不均衡，下次需要注意；題敘過長也該反省，原本為了避免歧異並強調容易忽略的條件才會多強調幾次同樣的敘述，但反而造成敘述過長、閱讀成本過高；因為和學校事情卡到，生成測資的部分也拖延了太多天，導致驗題完沒有足夠時間調整難度。

總之又一次創造了神話。

## 和善的裸題（但還是滅台）：[樹上最大遞增子序列](https://hackmd.io/@apcs-simulation-/r1E5jeNLye)

初試鋒芒便連續滅台三次，所以一月我被禁止出題了QAQ。
但營隊模擬賽缺人，所以我去出了 p4（禁了但沒完全禁）。

看營隊的課表有教到樹、LIS，我就想到在第十屆氣球杯比過的一題：

> 給點帶權有根樹，求所有根鏈 LIS 長度。

解法就是一邊 DFS 一邊維護 LIS 就好，求 LIS 的 patient sort 可以輕易 undo。

畢竟是營隊題目，大部分學生應該都是初學者，所以我子題給得很甜，題敘也直接放裸題（甚至還幫他們複習了一下樹和序列的相關概念）。

最終仍然滅台，最高分 90% 的一位在實作時寫出了懸掛指標（原本指向 `vector` 中值的指標在 `vector` 擴容後失效，導致 UB），喜題 WA。

且因為是營隊題目，我這次充滿幹勁地寫了很詳細的題解和 Generator 介紹，這也是我第一次開始記錄 Generator 的設計過程。

沿襲上次的趨勢，Generator 更加地模組化，我甚至將隨機生成樹的部分拆分出來做成一個小 module，且這也是第一次我將每個測資點的隨機種子隔離，以達到更好的復現、debug 效果。而且這次生成的測資完美且穩定地符合子題需求，總之我對這題非常滿意。

## 第一次沒滅！[單＿＿空](https://hackmd.io/@apcs-simulation-/rkdLSLVKJg)

> 給一些字串，按照第一個和最後一個字元的字典序分組並排列後，每一組內再按照字典序分組，最終分欄格式化輸出。

簡單（算得上有趣？）的單純字串實作題。Python 超級好寫，但 C++ 可能會稍微坐牢的題目，其實就是變相呼籲大家都來學 Python 的意思啦嘿嘿！

相較於 MineCRAFT 巨複雜的超噁實作，這題簡直是大巫見小巫，但我仍舊秉持著一樣的高標準把能卡的 edge case 全都卡得死死的，但只要好好看題述、好好跑範例測資就不會出問題。總之最終很多人通過此題，也是我第一道沒有滅台的題目。

## 假解王：[大智慧學苑的升旗典禮](https://hackmd.io/@apcs-simulation-/Sy3UDGk9kx)

> 給無向圖，要將點分組，求「組內節點之間皆不含邊」的最大、最小組數，不可能則輸出不可能。

這題是我在日常寫 LeetCode 時刷到的，[原題](https://leetcode.com/problems/divide-nodes-into-the-maximum-number-of-groups/) 只有要求最大組數，而我加入的最小組數則是要考二分圖判斷。本身概念非常簡單，就是枚舉每個點為起點 $O(V + E)$ BFS，總時間複雜度 $O(V \times (V + E))$，從題目的 $n \le 500$ 也能很好看出是這個複雜度。

然而這道題乍看之下（不看範圍）真的有那麼點能 $O(V + E)$ 解出來的樣子，我當時寫到這題也是落入了這個陷阱，因此最終決定出這題，讓大家深刻了解到**該好好看數據範圍**。

結果真的很多人寫出了 $O(V + E)$ 的假解，在模擬賽結束的幾分鐘才有人恍然大悟提交了 AC 解，讓這題不至於滅台ww。

這題的測資卻很難把時間複雜度卡滿，我最終分成節點數 $\approx \sqrt{500}$ 的一些小連通塊、和 $\approx 500/2$ 的一個大連通塊，主要是希望能讓 BFS/DFS 遍歷單個連通塊寫爛的人 TLE，但不太實際就是了，這題主要卡的還是 WA。

## zkw 是我的信仰：[大智慧學苑的午餐時間](https://hackmd.io/@apcs-simulation-/Sy34QfAskl)

> 給一個正整數 $n$，一顆維護長度 $n$ 數列的 zkw 線段樹，這個數列的各個區間依序可以用哪幾個 zkw 上的子樹表示？

（這個簡易題述寫得有夠爛，不知道怎麼敘述才能簡短又清楚 qwq）

那段時間在研究 zkw 線段樹如何像普通線段樹一樣 $O(\log_2 n)$ 二分搜，先說結論，第一種是依照本題的方法，找出所有大子樹，依序遍歷這些子樹的根找到答案所在的子樹，再像普通線段樹一樣對這個子樹二分搜；另一種是把 zkw 塞入額外節點（等於維護 $2 ^ {\lceil log_2 n \rceil}$ 長度的數列），使其變成完美二元樹，就能直接二分搜，這樣的 zkw 也能達到 $O(1)$ 全局查詢之類的，總之性質更好，但就失去 zkw 壓常的意義了。

稍微觀察可以發現答案長度的量級 $O(\log_2 n)$，其實就是在 zkw 上進行全局查詢（查詢 $[0, n)$ 區間）時會用到的節點。

這題就是稍微觀察，然後進行位元運算在樹上遍歷就能算出來，甚至有 50% 的子題 $n \le 1e5$，允許線性依照題意模擬的解通過，真的超級佛心。但也讓我發現真的很少人懂得撈子題，最終只有一人 AC，他是從根節點遞迴，判斷當前子樹是完美二元樹則輸出，也行。

這題會僅有一人 AC 還是這場本身超級冷清的問題，不只因為 Judge 硬碟掛掉而延期一週，又因為是寒假期間而很少人上線，悲劇啊TAT。

這題的 Generator 就是我手打了 $20$ 個二進位數字（並稍微加入一些 pattern，防止有人用假解唬爛）。數據範圍 $n \le 8.2e9$ 除了是在玩梗世界人口以外，也是為了把沒開 `long long` 的人卡掉（邪惡奸笑）。

## 有點懷念滅台...：[暴力又被TLE 想讓人滅台](https://hackmd.io/@apcs-simulation-/Hy15dPwyee)

已經 $3$ 題沒滅了，所以打算出一題噁心滅台題。其實是想要致敬 APCS p3 考古題 [磁軌移動序列](https://zerojudge.tw/ShowProblem?problemid=k733)，這我曾經的夢魘...

> 輸入一個字串，其中用 `a-z` 表示 $26$ 進位數字，並以 `_` 分隔，會有特殊指令 `R[]` 和 `Rn[]`，前者會將 `[]` 內的數列順序倒轉、後者則會將 `[]` 內重複 `n` 次。將字串轉換為數列 $a$ 後，由左而右紀錄每種數字最後一次出現的位置，對於每個 $a_i$ 求他的數值乘上「其與每種數字（包括上一個自己）最後一次出現的距離總和」，再將這些乘積加總。

一看就是大實作，而且還是 String parsing，細節超多，又因為有 `R[]` 倒轉操作，而必須建出 AST 抽象語法樹，並在樹上遍歷。

理論最佳解應該是 $O(\text{depth of Rn[...]} \times n)$，每一層 `Rn[]` 可以用數學推，不用將迴圈暴力展開，然而將內層迴圈的資訊更新到外層還是最差 $O(n)$，但我沒寫 :D。

我自認前 50% 的子題給得非常甜，但沒人撈，最終沒有任何人類拿分（有 AI 參戰，這題理論上 AI first try 能拿 50 以上，但他的 AI 可能偏笨，只拿了好像 20、30）。

這次的 Generator 巨巨巨巨難寫，是最難寫的一次，我最終寫出來的邏輯也沒有很好，成功率不高所以一筆測資大概要嘗試 10 幾秒，但能用就好了。然而測資的強度我很有自信，預期 TLE 的解我全都卡到 $1e10$ 運算量以上，十分好 :D。

各子題的詳細題解、Generator 的詳細設計在標題超連結的文件中寫得超級好（我自己很滿意），對這題有興趣的話很推薦去看看（裡面還有橘子寫的解，包含使用 xor-linked-list 處理 `R[]` 的有趣解法）！

標題是在捏他《輝夜姬想讓人告白》，但好像沒什麼人注意到...

## Generator 大進化：[小伊卡合成](https://hackmd.io/@apcs-simulation-/rk0_Tz3Wxx)

> 給一個數列，$k$ 次操作可把任意數 $+1$，求 $k$ 次操作後數列最大積？

這題也是從 LeetCode 上改過來的，[原題](https://leetcode.com/problems/maximum-product-after-k-increments/description/) 的 $k \le 1e5$，實際上可以做到 $O(n \log_2 n)$ 所以 $k$ 可以很大，所以我就把 $a_i, k$ 的範圍都變大了。

Solution、Generator 的詳細解說一樣可以到標題連結閱讀。這題的數據我原本卡得挺有自信，只要少個地方忘記開 `long long` 或者少 $\text{mod}$ 一次，全部的測資都會 WA，而且預期 TLE 的解幾乎都卡上 $1e10$ 運算量。但賽後發現有人拿了 55%，有個測資點的數據卡得不夠死，而使這個我沒特別卡到的假解沒有 TLE，所以不能嫌麻煩、存有僥倖心理啊...只要稍微覺得偏弱就得重生測資！

雖然這題跟上一題是同一場，Generator 是一起大進化的，但~~這題太普通讓我沒有標題可以下~~。在我高二下自主學習 [使用 Python 開發輔助測資生成的套件](https://hackmd.io/@ericshen19555/generator_helper) 初步完成後，我將其打包成一個 module 以供我生測資時能直接 import 使用，因此 Generator 的撰寫效率、可讀性、可維護性皆根本性地大幅提升，雖然還有不少地方值得修修改改、加入新功能，但現階段我已經十分滿意！

## 水題！沒理由滅！：[Bob 的答案卡](https://hackmd.io/@apcs-simulation-/SJQcOFrNel)

這題最令我驕傲的還是超有趣的題述，資工圈的讀了肯定能莞爾一笑ww（所以趕快點上面的連結看看！）。

> 給一些單選和多選題，Bob 依序寫了部分題目，但他忘記自己跳過了哪些題目，依序配對答案和題目，其餘以空白填答計算，輸出最高和最低可能的成績。

忽然想到這個挺有趣的 idea，其本質就只是單純的帶權 LCS 型 DP。

原本想說寫幾個假解的貪心策略，然後把他們卡掉，但後來發現貪心沒有比較好寫就作罷了。因此這次的 Generator 就是將數字開大一點、存在足夠多空白填答以使枚舉剪枝大概率 TLE。

慚愧的是我原本寫出的 AC 官解被橘子發現是 WA 假解，我原本認定的 base case 其實也是需要轉移的狀態（最後把我的這個 WA 解全部卡掉了）。總之真的得好好對拍！

20% 子題超級無敵佛心，簡直是 p1 難度的「沒有空白填答」，完全不用 DP，只要線性對答案計算成績就好，是我對「沒有人懂得捞子題」惡習的最大控訴！

然而不知道是題述太好笑，讓大家愛不釋手、反覆閱讀而沒時間實作，還是暑假開始而沒人參加模擬賽（淚qq），總之儘管這題 DP 很簡單，最終仍無人 AC，但有人撈 20% 子題讓我很欣慰。

雖然題述很有趣瘋狂玩梗，卻引發了「題述重點太零散」的問題，不管如何這點也是今後要多加注意的。

## Educational：[更簡單的石板（Super-duper Easy-peasy Puzzel）](https://hackmd.io/@apcs-simulation-/rJgz4Y8Ueg)

這題因為要放在營隊，所以我就想說出一點「具教育性質」的題目，原本想說像是上次營隊中出的 [樹上最大遞增子序列](#和善的裸題（但還是滅台）：樹上最大遞增子序列) 一樣，來一點樹 + 二分搜或其他演算法的梗，於是寫了一題樹上卡丹，但被嫌放在營隊太難了，最終被廢案。

後來我又想到了這題，啟發自我選修的 [高二運算思維課程](https://hackmd.io/@ericshen19555/while_high2_do_NPH#煙火-202559)，同時也是 CSES String Algorithms 章節中的第一題 [Word Combinations](https://cses.fi/problemset/task/1731)，基本的計數型 DP + 一點點字串，同時可以補充很多跟字串有關的技巧，像是 Rolling Hash、Trie、AC 自動機，十分具有「教育性質」，因此最後就決定放這題，題述部分則是和 [太簡單的石板](#滅台之咒：太簡單的石板) 做了呼應（其實就是太趕了沒時間再生一篇題述 (・∀・)）。

> 求字串 $s$ 有幾種被字串 $t_{1 \sim k}$ 拼接而成的方式？

這題的 Generator 說實話十分難搞，畢竟是字串題，純隨機的數學期望下想要卡到 worst case 不容易。我最後是想到了一種挺複雜、實作起來有夠麻煩的方案，能夠確保答案足夠大，而且字串本身也足夠「多元」，先隨機出一些短字串，並重複多次後，各自稍微切掉頭尾幾個字元，最後連接成 $s$；$t_{1 \sim k}$ 則大致同理，只是拼接出的字串長度較短，最難的部分在於「確保這些 $t$ 能恰好拼成 $s$」，因為這件事在數學期望上機率十分低，我會盡量挑「有其他 $t$ 在這裡結束」的地方當作下一個 $t$ 的開始點，再稍微微調機率參數，最後測資強度有達成還算滿意的水準。

這題最終只有一人解出，還沒有好好看數據範圍而砸了超綱的 Trie，因為此題還有一個十分具有「教育性質」的陷阱：輸入的 $t$ 可能會有重複，而使用相同的字串只能算一種方案，似乎有不少人踩到這個雷而被卡到 WA 0%，看到他們賽後恍然大悟的樣子讓我十分欣慰。

為了貫徹教育性質，此題的題解我也花了不少心思認真撰寫，可惜營隊因為時間進行有點延誤，而讓我沒有足夠時間教大家種 AC 自動機 qwq，虧我放學狂奔回家題解。

## 似乎有點超綱（汗）：[Python 的依賴管理簡直大🉐️](https://hackmd.io/@apcs-simulation-/rJT4emmwle)

這題的題述也十分有料ww，推薦閱讀。

幾個月前在資訊之芽營隊學到了 SCC 和 2-SAT，真心認為 2-SAT 十分有趣，但 SCC 演算法超綱，所以我就想說放寬時限，讓 $O((n + m) ^ 2)$ 處理 SCC 的解法也能過，這樣肯定就沒有超綱問題了！（深信 2-SAT 的難點在於縮 SCC）

而這題不只是一般的 2-SAT，而是要輸出「字典序最小的解」，會多一個 $O(n)$ 項由高位開始枚舉可行性，因此最後放行 $O((n + m) ^ 3)$。

> 給 $n$ 個套件，有些套件必取，有些套件必須同時選或同時不選，有些套件不能同時選、有些套件兩者至少選一，求名稱字典序最小的選擇。

我自認為把這題出得盡可能有趣：20% 枚舉基本分，也是最終唯一有人拿的子題TAT；20% 沒有「不能同時選」的限制，所以極為單純；20% 沒有「兩者至少選一」變成獨立集問題，但因為可以貪心取所以也很簡單；剩下的完全解只有 40%，甚至不到一半。然而因為在暑假中期，參加人數極少，最後大家都只有拿枚舉分（淚）。

測資生成的部分，這題這樣的限制下其實不太好卡時間，因為有「必取」這樣簡單明確的條件，而使需要考慮的方案數量遽減，再加上要放行 $O(n ^ 3)$ 解法，數字不能放太大，最後是確保：遍歷一次後能算出的必取、必不取者扣掉，剩下至少 $30$ 個要用 2-SAT 的概念考慮，至少不會被枚舉水分數。這題讓我深刻了解，這種條件約束的題目測資真不好生啊...

## Treap <3：[超陽春文字編輯器](https://hackmd.io/@apcs-simulation-/rJIZhLuFgg)、[Treap 好ㄘ（Treap is GOD）](https://hackmd.io/@apcs-simulation-/rkrh1iZYee)

這兩題都是 Treap 裸題，要放一起講。

因為暑假參加營隊終於學會了 Treap，想要來推廣推廣，之前又有想出一點看似要可持久化，實則沒有強制在線而可以離線後版本樹遍歷之類的東西，就先出了一題：

> 支援操作：移動游標、按下/鬆開 shift 鍵（配合游標移動區域選取）、輸入字串、刪除前後或選取區域的字元、全版本可持久化。

看似是可持久化 Treap 裸題，實則離線後建版本樹，字串部分用 Doubly Linked List 或兩個 Stack 實現，只是有點大實作。首先 shift 的部分直接被吐槽太難而被拿掉，而「離線」這個考點在 APCS 也從未出現，因此覺得大概率會滅台，最終這題慘遭廢案。

但我還是想考 Treap 啊！忽然想到前陣子打 LeetCode 週賽解到的一題，要根據操作反推數列某個位置的值，再想到營隊時有一題看似很難的題目（區間 sort），但查詢只有 $1$ 筆而變得很簡單。最終有了以下 idea：

> 支援操作：區間翻轉、區間交換、區間取代、區間賦值、區間加值，最終查詢某些位置的值。

數列原長可能到 $1e9$，經過 $1e5$ 個操作甚至可能到 $1e14$，然而只有查詢最多 $10$ 個位置。因此可以從查詢點反著執行操作，「時間回溯」到原位置。這題應該是我出過最「好好思考」的有趣題目，有點 Codeforces 味。

測資的部分，基本上採取純隨機的形式，相信機率分布會幫我把所有 edge case 卡好，但我似乎忘記只有查詢 $10$ 個位置的事實...導致最終卡 WA 假解的能力偏弱，但 `long long` 卡滿卡死，而時間上更是做到五個操作中「任一個操作寫爛」都會跑到 $1e9$ 以上的計算量。

題述部分我更是煞費苦心，通篇「這是 Treap 裸題，請抓緊時間實作你的 Treap！」，甚至「貼心」地附上了好幾點實作可持久化懶標 Treap 時要注意的細節，造成了十分搞笑的意外效果：丟給 LLM 後他們無一例外、屢試不爽地狂砸 Treap，縱使有提供「詢問 $\le 10$」的資訊，然而這一句雖然短卻能極大扭轉題目難度的重要資訊從沒被 Transformer 架構「注意到」，再加上這題的操作有點複雜，LLM 砸出來的 Treap 幾乎都爛了。此題竟意外成為防 AI 好題ww。

然而真的有參賽者在賽中砸 Treap 但爛了一些只拿 90%，我不知道他是拿網路模板還是丟給 AI，總之他很壞 :(。大家似乎並不擅長好好思考，最終此題滅台。

而人手有些不足，沒人出 p2，所以我就把上面的文字編輯器數值縮小，變成純模擬可過的簡單 p2。

在兩題的題解中，我都補充了一些 Follow Ups：支援更多操作、數值範圍變大...之類的，最終無一例外導向 Treap，身心暢爽！