# 建中校隊初選題解

## Rejudge!
1. $K = 0$的情況只是在問每個隊伍的排序而已，純粹是個閱讀測驗+實作。
2. 枚舉$2^M$種rejudge的狀況，再枚舉每筆submission計算每個隊伍的排名，複雜度$O((S+N)2^M)$。
3. Submission太多了無法枚舉，不過顯然不需要。直接紀錄每個隊伍每一題有Rejudge或沒Rejudge的penalty跟解出與否，枚舉的時候直接$O(NM)$看排名。複雜度$O(NM2^M)$，看起來有一點點大但是可以AC。
* 注意算名次不需要排序，雖然在這裡對總複雜度沒什麼影響。

## 字串構造

1. 7分：直接產生前$K$個字母的子集的排列，再隨意接在一起。
2. 要改成20分也相當容易：顯然長度不足$K$的子集排列一定會是某個長度為$K$的子集排列的子序列，因此只要把長度為$K$的排列接起來即可。長度是$K\times K!$。
3. 47分：random產生足夠多的字元（評分規則有寫bound是$2K^{2.5}$，可以直接random到這個數量），那他符合題目要求的機率超過99.9%。
4. 59分：考慮greedy的做法，每次選擇會造成最多尚未出現的排列的字元，好好實作的話可以在時限內通過第四筆subtask。
5. 把前$K$個英文字母重複$K$次（如`abcdeabcdeabcdeabcdeabcde`），即可包含所有$K!$種排列，因為可以在$K$組都各挑一個需要的字元。長度$K^2$，80分。
6. 可以注意到其實只要重複$K-1$次，後面再接一個`a`即可，因為如果相鄰兩個字母是順序的，那可以把那兩個字母塞在同一組；如果都沒有，那最後一個字母會是`a`。長度$K^2-K+1$，100分。
7. 構造方法為`abcdefg a bcdef a gbcde a fgbcd a efgbc a defgb ac`，長度$K^2-2K+4$，125分。

實際上，給定$K$，要找出<b>最短</b>符合條件的字串是coNP-complete問題，目前沒有有效率的演算法，對於$K\geq 8$甚至可能還沒有人知道最短符合條件的字串長度是多少。可參考[OEIS A062714](https://oeis.org/A062714)。

## 最長回文子序列
1. 直接枚舉每種子序列，共有$2^N$ 種，再花$O(N)$時間檢查是不是回文。
2. 考慮DP的做法
* 令$dp(l, r)$代表字串$S[l]$到$S[r]$的最長回文子序列有多長
* $dp(l, r) = \max(dp(a + 1, b - 1) + 2), l \leq a \leq b \leq r, S[a] = S[b]$
* 狀態$O(N^2)$、轉移$O(N^2)$、總複雜度$O(N^4)$
* 理論上是21分，可是驗題者用這個做法不小心撈到34分
2. 實際上不需要$O(N^2)$轉移
* $dp(l, r) = \max(dp(l + 1, r - 1) + 2(s[l] == s[r]), dp(l + 1, r), dp(l, r - 1))$
* $O(N^2)$
* 71分
3. 只有0~9十種字元，答案又要求輸出不超過1000，因此當長度至少10000的時候一定有一種字元出現超過1000次，全部都是相同字元所形成得字串是回文，所以小於10000的使用上一筆Subtask的做法，否則任選一出現超過1000次的字元輸出，100分

## 排水系統管理
1. 只要求精確到小數點下兩位，又保證時間若非無限則小於1000，所以可以枚舉答案(0, 0.001, 0.002, .... , 1000)，每次再看現在時間有哪些閘門是開啟的，11分。
2. 同樣枚舉答案，不過$N$太大不能枚舉每個閘門，不過其實可以對每個閘門照時間左界排序，每次將新開的閘門加入考慮，並注意淘汰時間過期，或是高度太高的閘門，詳細實作可以使用兩個set分別維護高度以及右界。
* 每個閘門只會進入兩個set各一次，也至多只會出來一次，因此總複雜度是$O(答案+N\log N)$
* 雖然保證時間不超過10000，不代表答案不超過10000，不過可以知道時間超過10000了以後只剩下可以無限使用的閘門，再將它們照高度排序後好好計算答案即可。
3. 保證每個時間只有一個閘門開啟，所以把他們排序直接算
4. 考慮將所有閘門照左界排序，並將現在啟動的閘門照高度排序（使用heap或set，或者也可以開一個按照高度排序過的閘門順序的陣列）
* 每次會改變閘門數兩只有兩種情形：新的閘門打開了、某個閘門高度超過水面
* 兩種狀況取較近的做
* 複雜度$O(N\log N)$
5. 合併Subtask 2以及Subtask4
* 每次會改變閘門數兩只有三種情形：新的閘門打開了、某個閘門時間到了，某個閘門高度超過水面
* 做法相仿， $O(N \log N)$

## 連續乘法計算
* 這題的梗是輸入的序列有可能包含0或負數（仔細看題目！），如果沒有考慮到這一件事的話你只會在每個subtask拿到一半的分數。
1. $N\leq 4$，可以在code裡面把所有可能的詢問都寫出來之類的，6分(?
2. $N\leq 30$，代表所有數字乘在一起也不會爆double範圍（double範圍到$10^{308}$），所以直接用double算就好了，36分。
3. $N\leq 400$，在TIOJ上這剛好不會爆long double範圍，58分。
4. 內建浮點數在這個subtask都會爆範圍，但是注意我們只需要求出近似值，所以我們可以預先把所有數字取以10為底的log，查詢時改用相加的。輸出答案的時候，指數部分直接拿log的整數部分，真數部分則把小數部分取以10為底的指數後輸出即可。（這裡printf的用法可以是`printf("%.10LfE+%d\n", a, b);`。）複雜度$O(NQ)$，70分。
* 因為0或負數取log會爆掉，所以要開另外一個陣列紀錄每個數字是不是0或負數，再把最後輸出的結果作正負號調整或直接輸出0。
5. 注意到做法4其實只是求區間和，所以可以預先算好所有的前綴和，每次查詢就可以$O(1)$回答了，總複雜度$O(N+Q)$，100分。（很抱歉線段樹的複雜度是爛的，而且空間也太大。請不要看到區間和就直接把線段樹寫出來，這是一個糟糕的習慣XD）
* Subtask 4, 5用正常作法的話需要用long double才能達到所需的精度。但使用double並用一點不同的求和方法是可以避免誤差而AC的，詳請請自行google "Kahan summation algorithm"。

## 螺旋的因果律
1. $N \leq 8$直接$O(N\times N!)$枚舉。
2. 觀察到$N$一定要放第一個，因為$N\equiv 0 \pmod{N}$，如果不放第一個的話會出現連續兩個相同的前綴，$O(N!)$。或者你用Subtask 1的作法，在本機算完答案後直接放code裡輸出也是可以。
3. $N$如果是2的冪次的話，$(N, 1, 2, 3, \ldots, N - 1)$或$(N, N-1, N-2, N-3, \ldots, 1)$都是一組解。
4. 首先，$N$為奇數時無解（$N = 1$除外）。
* $N$為偶數時構造前綴為$(0, N-1,1,N-2,...,N/2-1,N/2)$，不難驗證這個是一個解。