owned this note
owned this note
Published
Linked with GitHub
# 建中校隊初選題解
## 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)$,不難驗證這個是一個解。