選訓一天一 OI 計畫 #1 ><

賽前

因為這場是在選訓 vir 的，所以時間上是 10:00 ~ 中午吃飯 ~ 15:40，維持總時間 4 小時。

賽中

記得 JOI 是有按照難度排序的，所以開場先讀 A

• A Just Long Neckties
  給你長度是 $N + 1$ 的 $A$ 陣列跟長度是 $N$ 的 $B$ 陣列，定義一個配對 $A_i$ 對 $B_j$ 的奇異度是 $\min\{A_i - B_j ,\, 0\}$，
  對每個 $A$ 陣列的元素輸出把他拔掉之後，所有 $B$ 陣列的都配對完的最小最大奇異度。
  $1 \leq N \leq 2 \times 10^5$
  [1] $N \leq 10$
  [8] $N \leq 2000$
  [91] 無額外限制

大水題，sort 之後對前綴後綴做完就 AC 了。

00:08 A 100

$\newline$

寫完之後繼續往下讀，

• B JJOOII 2
  輸出湊出剛好是「J 重複 $K$ 次、O 重複 $K$ 次、I 重複 $K$ 次」的字串需要最少多少時間。
  $3 \leq N \leq 2 \times 10^5,\, 1 \leq K \leq \frac N 3$
  [1] $N \leq 21$
  [12] $N \leq 3000$
  [87] 無額外限制

一開始怎麼想都只會做兩個，但後來發現其實只要不斷做 sliding window 就做完了，打錯字 WA 超多次，還好都有找到。

00:36 B 100

$\newline$

• C Collecting Stamps 3
  你在一個長度為 $L$ 的圓圈上，第 $i$ 個收集站在 $X_i$ 的位置，如果你在 $T_i$ 之前抵達可以收集到第 $i$ 種郵票，
  輸出你可以最多拿到多少種郵票。 $1 \leq N \leq 200,\, 2 \leq L \leq 10^9,\, 1 \leq X_i < L$
  [5] $N \leq 12,\, L \leq 200,\, T_i \leq 200$
  [10] $N \leq 15$
  [10] $L \leq 200,\, T_i \leq 200$
  [75] 無額外限制

稍微想一下就可以列出這個狀態：
$dp_{i,\,j,\,k,\,0}$ 表示你已經走過 $[i..j]$ 並且得到 $k$ 分的最短時間，最後停留在 $i$，
$dp_{i,\,j,\,k,\,1}$ 則是最後停留在 $j$，
把環狀拓展成兩倍然後注意 $j - i < N$ 就好，過程中迴圈順序搞反 WA 了一次，最後過了。

01:07 C 100

$\newline$

• D Olympic Bus
  給你一張 $N$ 點 $M$ 邊的圖，走第 $i$ 條邊的花費是 $C_i$，反轉的花費是 $D_i$，你最多能反轉一條邊，
  問從 $1$ 到 $N$ 再回來的最小花費，或決定不可能。
  $2 \leq N \leq 200,\, 1 \leq M \leq 50000$
  [5] $M \leq 1000$
  [11] 所有的邊都剛好有偶數個複本
  [21] $C_i = 0$
  [63] 無額外限制

一開始 naive 的做法是直接暴力然後每次做 Dijkstra，但這樣複雜度是 $O(M^2\log M)$ 或 $O(MN^2)$，顯然不會過。

後來想一想了很久發現有些邊似乎可以偷懶不要做，於是就有這個做法：

• 先跑一次最短路，還有反過來的最短路
• 對每條邊如果有在已經找到的最短路中，重算，不然就利用正的反的計算答案。
  這樣一來複雜度是 $O(M + N^3)$ 或 $O(NM \log M)$，實作有點小繁雜但整體來說還可以，所以我就先去吃飯然後再回來實作了。

（回來的時候 PixelCat 睡著了）

03:21 D 100

$\newline$

這時候還有快一個半小時可以做 E，於是我就開始全力做：

• E Fire
  給定長度為 $N$ 的陣列在時間 $0$ 的樣子 $S_i$，每秒如果該陣列左邊的元素比他大，他就會改成他左邊的元素。
  $Q$ 筆詢問在給定時間 $T_i$，$L_i$ 到 $R_i$ 的區間和。
  $1 \leq N,\,Q \leq 2 \times 10^5,\, 1 \leq T_i \leq N$
  [1] $N,\,Q \leq 200$
  [6] $T_i$ 相同
  [7] 單點查詢
  [6] $S_i \in \{1,\, 2\}$
  [80] 無額外限制

看完的時候推一推發現每個人影響的範圍都是一個平行四邊形，當下就有想到要用線段樹 + 掃描線維護，
但是一直想不到要怎麼維護斜的修改。

於是我就開始寫了子題看看有沒有幫助，$1$ 分用暴力、$6$ 分用 sliding window + 前綴和、$7$ 分用二分搜然後 $6$ 分用 BIT。
最後子題真的完全沒有幫助，燒雞。

03:55 E 1

04:10 E 7

04:16 E 14

04:24 E 20

$\newline$

Result

							Sum
A	1	8	91				100
B	1	12	87				100
C	5	10	10	75			100
D	5	11	21	63			100
E	1	6	7	6		80	20
Score							420

級距落在 400 ~ 499 的前 7 內。

賽後補題

賽後我把 E 成功補掉了，算是少數我可以補成功的 OI，
基本上就是把平行四邊形拆成三角形，然後三角形拆成矩形跟等差位移的矩形，所以總共要兩棵線段樹。
我還一直拿 BIT 區間修改區間查詢，笨死zzz

檢討

基本上打的還可以，除了屢屢出小 bug 以外。 但 E 基本上我應該要做出來，我被線段樹打爆。
希望模考可以好好寫出我應該要會的題目，

選訓加油 ><