CF EDU 137 Virtual 心得

前言

今天（10/17）請假在家，看到晚上有 EDU Round 就順便 vir 一下之前沒打到的 EDU 137（結果晚上因為頭痛把比賽 drop 了），覺得題目蠻有意思的就記錄一下

這篇應該就簡單紀錄一下開題順序、想法之類的，詳細的解題過程應該會再另外發一篇

賽中

PA

給一個 $n \times m$ 的西洋棋盤，問有沒有位置是騎士沒辦法走到其他格的。

想了一下發現最邊邊是最多選擇的，所以選中間（$(\lceil\frac{n}{2} \rceil, \lceil\frac{m}{2} \rceil)$）就好。想到解法後還一直想說到底有沒有那麼簡單，但畢竟是 PA，就直接送出去了。

PB

有兩個長度為 $n$ 的數列 $a, d$，其中數列 $d$ 是輸入值，其定義為：$d_1 = a_1, d_i = \lvert a_i - a_{i - 1} \rvert$，而 $a$ 是一個非負整數的數列，求是否有唯一解，如果有則將其輸出。

看每個 $a_i$ 是否有兩種可能，如果都只有一種那就是唯一解。

PC

有數字為 $1 \sim n$ 的卡牌，各分 $\frac{n}{2}$ 給 Alex, Boris。接下來每個回合兩個人會輪流先出，如果後出的人出的數字比前出的小，那麼前出的人就會贏得這場比賽，否則比賽繼續，問讓 Alex 贏、讓 Boris 贏和讓比賽平手的分配方式有幾種

看了這題之後感覺要不是 DP 不然就是數學題，但是我不會數學，乾瞪眼很久之後偷看一下記分板，發現 Pixel Cat 已經把 PD 解出來了，就跟著去解 PD

PD

有一棵樹，可以對它做 $k$ 次以下操作：

• 選擇一個點對 $u, v$（$u$ 是 $v$ 的父親），斷開這條邊，並將 $v$ 及其子樹連到 $1$

求 $k$ 次操作後這棵樹的高度最少是多少

這題最答案二分搜的作法還蠻好發現的（至少跟 PC 比起來好想多了），不過寫了一些智障的 bug，WA 3 次才解出來

PC

57 分鐘解完 PD 之後就回來看 PC 了，看到範例給了 $n = 2, 4, 6, 8$ 的解，原本想說可以從 $n-2$ 的解推出答案，但怎麼看就是看不出任何規律，乖乖想正規解法。

後來發現可以將答案拆解為不同回合贏的方法數，經過一番推導跟 debug，最後終於將這題寫出來。有趣的是送出的時間是 1:59:28，壓秒過好爽歐。

後記

這場題目都還算蠻經典的（？，至少沒有啥奇怪的梗題（雖然我覺得 PC 的 *1500 根本遠大於 PD 的 *1900），雖然結果不是很滿意（時間 + WA 有點多），拿下了 4/213 的成績，但至少 Performance 有 1865。希望面試前可以上 1900 qwq。