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

賽前

發現我不會算選訓時間，vir 改到 13:00 ~ 17:00。

賽中

開場先讀 A

• A Bitaro the Brave 給你一個 $H \times W$ 的表格，輸出有多少數對 $(i,\,j,\,k,\,l)$ 滿足 $(i,\, j)$、$(i,\, l)$、$(k,\,j)$ 分別是 J O I。
  $1 \leq H,\,W \leq 3000$
  [20] $H,\,W \leq 100$
  [30] $H,\,W \leq 500$
  [50] 無額外限制

大水題，隨便做個前綴和就過了。

00:08 A 100

$\newline$

• B Exhibition
  你有 $N$ 個畫作，第 $i$ 個有大小 $S_i$ 跟價值 $V_i$，另外有 $M$ 個畫框，第 $i$ 個有大小 $C_i$。
  你要挑一些畫放在畫框裡展覽，一幅畫 $i$ 能放入另一個畫框 $j$ 若且唯若 $S_i \leq C_j$，
  另外所有的組合中 $C_j$ 要非嚴格遞增，$V_i$ 也要非嚴格遞增，輸出最多能展覽多少畫。
  $1 \leq N,\,M \leq 10^5$
  [10] $1 \leq N,\,M \leq 10$
  [40] $1 \leq N,\,M \leq 1000$
  [50] 無額外限制

想很久之後只有先 sort by $V$ 跟 $C$，列出 $dp_{i,\,j}$ 表示考慮 $[i..j]$ 的畫，可以合法放進 $[1..j]$ 的畫框多少張，
然後觀察到 $dp$ 的更新是先 insert 一個東西對後面區間加值，
例如現在如果可以放進第 4 個畫框，$dp$ 的更新就可以寫成

	1	2	3	4	5	6	7
$dp_{i,\,j}$	1	1	1	2	2	3	3
insert	1	1	1	2	2	2	3
$dp_{i+1,\,j}$	1	1	1	2	3	3	4

一直想不到要怎麼每次維護，想來想去最後想到要一棵帶懶標的 Treap = =
但現在直接刻下去估計是會直接燒雞，所以就決定跳題看 C 了。
（Blog 寫起來感覺很少，但實際上這裡耗了快半小時）

• C Growing Vegetables is Fun 3
  你有三種植物 RGY 總共 $N$ 棵排成一排，你可以交換相鄰兩個，求出使同種不相鄰的最小交換數，或決定不可能。
  $1 \leq N \leq 400$
  [5] $N \leq 15$
  [55] $N \leq 60$
  [15] 僅包含 RG
  [25] 無額外限制

稍微想一下有列出狀態：
$dp_{color,\,i,\,j,\,k}$ 表示已經決定了 $[1..i]$ 的結果，含有 $j$ 個 R 跟 $k$ 個 G 以及 $i - j - k$ 個 Y，
其中最後放的顏色是 $color$。
轉移就可以好好計算另外兩個的逆序數對數量，然後用前綴和加速就可以做到 $O(N^3)$，

00:59 C 0

$\newline$

得到了一堆 TLE 跟 WA，
接下來就稍微壓了一下狀態數跟 pragma，總算是把 TLE 先處理掉了，剩下就只剩轉移燒掉要處理而已，
修了一下才發現我忘記紀錄 $color$，把他實作上去得到

01:07 C 15

$\newline$

過了只有兩個的 case，又修了一下沒過，
這時候心態基本上快崩掉了，但還是要好好繼續寫所以就先去看了 D

• D Coin Collecting
  你有 $2N$ 個金幣在座標平面上，$1$ 單位時間你可以移動其中一個到相鄰的座標，金幣可以重疊，
  你要把他們都移動到 $(1,\,1)$ 到 $(N,\,2)$ 的矩形內一格各一個，問最小時間。
  $1 \leq N \leq 10^5$
  [8] $N \leq 10$
  [29] $N \leq 1000$
  [63] 無額外限制

感覺是有點小麻煩的題目，先回去看 B

接下來就 BC 大概半交替的想，就又過了快一個小時，

之後發現因為 $dp$ 值在同一個 $j$ 下遞增，所以可以直接做到結束再算最大值，
最後就直接開砸 pbds 模擬，就過了 ><
我根本在耍毒= =

01:43 B 100

$\newline$

大概心態就回來一半了，決定好好把 C 的 bug 抓出來，
看很久之後發現我逆序數對算錯東西，做了另一個找座標的之後對範測發現都變兩倍，
結果是我逆序數對忘記除以 2 = =
我一開始如果有發現這件事就不會燒到這個時候了，應該早早就知道我 DP 有爛掉轉移了。

01:54 C 100

$\newline$

這時候回來看 D，又想了很久，

發現可以先做必要的步驟：也就是左下先走到 $(1,\,1)$，左上先走到 $(1,\,2)$，然後剩下依此類推。
稍微構了各種 case 就想到一個 greedy：
從 $1$ 掃到 $N$，如果有人多另一個人少就往上／下移動分給它，不然就繼續累計。
這樣傳上去就過了 OAO
心態大噴發

02:45 D 100

$\newline$

• E Unique Cities
  給定一棵 $N$ 個點的樹，每個點有顏色 $1 \leq C_i \leq M$，定義對 $x$ 節點而言，$y$ 節點被稱為獨行城市表示沒有任何其他 $z$ 節點使得 $x$ 到 $y$ 的最短距離跟 $x$ 到 $z$ 的最短距離相同。
  求出所有節點的獨行城市的顏色種類數。
  $1 \leq M \leq N \leq 2 \times 10^5$
  [4] $N \leq 2000$
  [32] $M = 1$
  [32] $M = N,\,C_i = i$
  [32] 無額外限制

看完的時候完全沒任何性質可以用，亂衝亂寫了一個 dsu on tree 換根但本機吃到 RE，
de 不出 bug 就決定直接撈暴力，

03:50 E 4

$\newline$

然後比賽就結束了-w-

Result

							Sum
A	20	30	50				100
B	10	40	50				100
C	5	55	15	25			100
D	8	29	63				100
E	4	32	32	32			4
Score							404

級距落在 400 ~ 449 的前 1 內（？？？？

賽後補題 + 檢討

基本上整場有夠燒雞，果然再次證明心態穩住就一定有機會，
賽後去問的 alvingogo B 的乾淨作法，發現是簡單 greedy，
我到底在耍什麼毒= =

後來也去問了 abc E 的關鍵想法，我覺得我應該是要想到這個東西的 qwq

總之這場打得有夠爛，但 Rank 真的有點扯 OAO

選訓加油 ><