前言

這是我參加TOI2022初選考試後的心得。本次考試只拿了26/500分，排名好像兩三百名的樣子，相當慘不忍賭。雖然我弱弱的但是還是覺得有些東西應該要記錄起來。

題目

  • 迷宮出口
  • 打鍵盤
  • 共享單車
  • 2022
  • 間諜

以下來逐一介紹每題還有我的心得。

迷宮出口

敘述

給你$n(n\le 2500)$個點，代表圖騰的方位，還有一個半徑$r(r\le 10)$，代表吟唱咒語可以影響到的半徑，問你在有幾個格子點，在那些地方吟唱咒語可以讓奇數個圖騰被觸發(吟唱咒語的概念為以某一點為圓心，半徑為$r$做一個圓，但凡被圓覆蓋到的圖騰就算被觸發)

想法

我一看到這一題，心理os:這TM來計算幾何阿!我剛剛來的路上才在葛瑪蘭上面看邏輯腦的計算幾何。相當麻煩。$n\le 2500$好像可以枚舉的樣子，可是好像要排序，然後就去看其他題目了。

真正在解題的時候，我發現第一子題組的分好像很好偷，因為$n=1$，於是我就去偷第一子題組的分數，然後就WA了…(十筆測資被卡最後一個)

當時我心想，這TM不太對吧…我明明都算對欸，後來想說是不是不能在圖騰上面吟唱，因此，修改了一下，然後十筆測資一個都沒有過…然後我就不信邪了，開始瘋狂嘗試，甚至用到了assert函式(當下懷疑第十筆測資有問題)，結果他不給我assert，我只好慢慢看。看著看著，我發現好像可以枚舉$r$的值，然後建表。因為只有一個圖騰，而且他是問你個數，所以是可以平移的!於是我建了一個表r[10]，其r[i]代表半徑為i時的解，然後，就莫名其妙過了，偷到了26分，也是我全場唯一的分數，相當感人。(最後我還是不了解到底哪裡出問題…)

打鍵盤

敘述

給你一串文字，問你打出這串文字花費的最小時間為何。你只能用兩隻手指頭，起點分別為’F’以及’J’，從鍵盤上某一格移動到相鄰的另一格需要花費一單位時間

想法

看到這一題的時候我有點錯愕，這種詭異的題目還是第一次看到。當下的第一個想法是:這是一個相當噁心的題目，因為鍵盤並不是工整的表格，因此，如果要建表的話會相當麻煩並且噁心。最終決定偷第一子題組的分數:所有字母都在同一排(AS…KL)上面。

實做起來發現確實挺麻煩的，因為這並不是一個單純的貪心，好像還要用到動態規劃的樣子，直接戳我弱點…。看似可以使用單純的貪心來解決這一個子題組，可是如果有一個按鍵和兩根手指的距離相等，就會出問題了。好像還有其他的問題，所以我在吃了兩個WA之後，就決定先放棄，畢竟這一個子題好像也才30分而已。最後這一題還是沒拿到分。

共享單車

敘述

給你一張有邊權的圖，還有每個節點初始的單車數量，叫你把每個節點的單車挪動，直到每個節點的單車數量恰等於$k$。求挪動單車的最小花費。(一輛單車經過權重為$w$的邊花費$w$)

想法

第一次看到覺得有點難，所以直接跳掉。後面再仔細看實發現其實並不會太麻煩。因為題目規定邊的數量等於點的數量減一，而且這是一張全連通圖。因此可以當作是一棵樹!每次優先處理樹葉的部分，因為樹葉處理起來簡單，處理完之後將樹葉剪掉，並且另樹葉的父親成為新的樹葉。尋找樹葉可以將每個點依照”跟他連線的點數目”排續。

即便如此，我還是被STL卡很久，不知道是已經寫了兩個小時讓我昏昏欲睡還是怎樣，在二維vector裡面放pair竟然忘記要給到第二個引數，浪費許多時間。在最後五分鐘終於過了兩筆範測，丟上去後跑到結束也沒有結果。最後還是沒有拿到分。如果我沒有花時間去搞第二和四題的話，這一題應該可以拿滿才對…。

剩下改天打，睏了…