最後更新日期 2024 / 01 / 01

TOI 新手同好會心得文

前往師大

有點怕遲到很早出門
結果正式開始前半小時就到師大了
不過教室已經開了
就到裡面坐著寫寫題

等工作人員準備一下之後
很快就開放參與者報到了
領了名牌還有幾個師大的紀念品
因為下午團體賽要分組所以也抽了組別的籤

個人賽

比賽時常 2.5 小時總共有 8 題
開賽後先打開了第一題
但看到一堆複雜的算式所以就先跳過了
第二題感覺就是排序裸題
但沒看很仔細導致看不懂題目所以也跳過了
第三題是字串模擬題
我決定從這題開始下手
結果因為最近用 Mac 而且家裡 Windowns 鍵盤跟比賽的差很多的關係
打字打的超痛苦
方向鍵位置差很多而且要按 ctrl 一直按到 alt
寫到心態很崩
這種水題傳上去甚至還吃了一個 WA
我甚至在想為什麼我要花時間來這裡受苦受難
重新看題目後發現原來完全理解錯意思了
修改一下之後總算 AC 了一題 \

翻開第四題
看到測資範圍到了 105
總算看到一題算法題了
大概花幾分鐘思考就把雙指針寫完
不過還是吃了幾次 WA
加上讀題跟 debug 大概總共花了半小時才 AC 這題

第五題
很明顯的水題目
簡單陣列操作而已
大概只花了幾分鐘就寫完這題
AC !

第六題
裸的 STL prority_queue 題
寫起來也還算順手
1 發 AC

接下來是第七題
但看起來有點難所以先看第八題
第八題是括號運算式 + 二分搜或枚舉
不過看起來實做有點麻煩
所以先回去看前面的題目好了 重新讀懂第二題之後花了一點時間就 AC 了

回到第一題
仔細看題目之後發現
原來似乎只是要模擬計算過程而已
不過浮點數感覺很棘手
總之還是先寫在說
結果傳上去馬上吃了一個 WA
花了一點時間 debug 之後獲得 20 分子題分數
不會有小數點精度問題的子題 qwq

最剩下半小時我決定來寫最後一題目
把括號運算式弄好了
枚舉也做好了
不過一直吃 WA
比賽就這樣結束了

總分:620
打的比上次還慘

午餐時間

先上一張超讚的午餐圖片

簡單來說就是比薩+飲料
然後系主任還有一個一個同學發巧克力 QQ 球
(系主任人超好 ><)

然後吃完午餐就是頒獎跟摸彩時間
結果意外的拿了個人賽第二名
獲得了一副藍牙耳機
摸彩還摸到前幾大獎
可惜前三名不能拿摸彩獎品所以重抽了

接著是神奇的團康小遊戲(?
他們會發給每個人一張表格
上面有很多格子
每個格子寫著不同內容
例如「我來自雲林」、「我近視不到 200 度」、「我知道 DFS」之類的
要找符合內容的人簽名
最後先連成一條、兩條、三條線的可以獲得獎品
總之我沒成功拿到獎品就是了 QAQ

團體賽

這次的團體賽玩的是 Same Game
簡單來說就是在盤面上找到兩個以上同色球連再一起消除得分
消除後空格會有上面的球掉下來
獲得越多分數的排名越高
不過跟一般的差別就在我們要使用程式操作這個遊戲

一剛開始的想法是
有沒有可能這就是某種很酷的 dp 題目
畢竟目前狀態消除不同位置都會讓不同的球往下掉
也就會改變未來的狀態進而影響結果
不過後來想了一下沒什麼頭緒
但看到了第一步可以花 20 秒計算
於是我就想說
不如來試試看 Minimax Algorithm
以前做遊戲的電腦 AI 時用過
想說感覺應該可以用在這邊
(其實簡單來說就是暴力枚舉 k 步後的所有狀態在選擇最佳的走而已)
花了快一個小時寫完後
結果才跑兩層記憶體就炸了 qwq
嗯 預測一兩步跟沒預測一樣
所以只好果斷放棄這個做法

想起剛剛在講解規則時
有提到一些策略
於是我們就先把那些能做的都做出來
主要就是兩個「先固定消一個顏色,消完再消下一個」跟「先把連通塊小的顏色消掉」
於是我們就拿了第三名 (???)

帶走了一個安妮亞滑鼠墊 : D

結語

整體來說還蠻好玩的
午餐很讚而且也帶了不少戰利品
還認識了一些人 (準確來說是只認識了一個人 TAT)

推薦文章

[題解] TIOJ 2195 粉刷護欄 (TOI 2021 初選 pC)

上下有個有一根木樑 然後中間有 n 條可能會相交的木板 找出最多可以釘上幾條木板並構造最大字典序的解 細節自己去 TIOJ 看 :因為這題看起來沒人寫題解 於是我就發了這篇文章 ouob仔細觀察問題 我們可以把問題轉換成 LIS 或 LCSLCS 的話應該不難理解 因為要釘最多木板其實就是要在上下兩條陣列各選一個共同的子序列 然後把每個數字一一對應釘起來 但是 LCS 需要 On^2 的時間複雜度才能計算 所以一定會 TLE接著是 LIS 的作法 仔細觀察題目的話可以發現 如果木板有"座標"的話 其實我們在做的事情就是"對木板做 LIS" 更精確一點的說 就是我們其實可以把木板在上樑的點跟下樑的點綁成一個 pair 做 LIS 我們說木板 A 的座標小於木板 B 代表 A 的下樑座標跟上樑座標都小於 B至於座標的部分大概就是這個意思: 以附圖為例 木板 3 的座標就是 2, 1 木板 4 的座標就是 5, 3 木板 5 的座標就是 4, 4如果用最普通的 DP 方式 就算能構造解也很難求最大字典序 於是我們修改一下計算方式 把轉移式改成 "定義 dpi 為把第 i 個元當頭素能構造出的 LIS" 其實就只是倒著做 LIS 然後 Increasing 改成 Decreasing 就好了做完 DP 之後 我們要從 dp 值大的開始構造 先找一個 dp 值跟最終 LIS 一樣長而且字典序最大的元素 接著往右找小一點的直到 1 為止關於上面提到的"座標" 實際上不需要真的把座標算出來 我們只需要把第二個陣列代表下梁座標的陣列每一個元素替換成該元素在第一個陣列出現的位置 並對第二個陣列做 LIS 就可以了 ~~原因的話講起來有點麻煩 自己想吧~~第一次傳 WA 了一片 然後 debug 的時後測出這樣的測資會出錯 如果你也找不到你的程式坐在哪裡的話 不仿測試看看這筆測資33 1 21 2 3cppusing namespace std;const int MAXN = 2e5 + 10; map 會超時,所以改 unorderedmapunorderedmapint, int rpos;unorderedmapint, int pos;vectorint lensMAXN;int vMAXN;bool cmpint a, int b { return rposva rposvb;}signed main { io; int n; cin n; for int i = 1; i = n; i++ { int tmp; cin tmp; 紀錄元素座標 postmp = i; } for int i = 1; i = n; i++ { int tmp; cin tmp; 將陣列的值設定為目前元素在上面陣列的出現位置 vi = postmp; 把坐標在映射回他的值,輸出的時候會用到 rpospostmp = tmp; } LIS 的部分 作法類似: int len = 0; vectorint dp; for int i = n; i = 1; i-- { int ans = 0; 儲存目前 dp 值:以 i 為開頭能構造出多長的 LIS if dp.empty || dp.back vi { dp.pushbackvi; 紀錄目前的 dp 值 ans = dp.size; } else { auto ite = upperboundalldp, vi, greaterint; ite = vi; 紀錄目前的 dp 值 ans = ite - dp.begin + 1; } len 維護最終 LIS 長度 len = maxlen, ans; 紀錄每個長度的解 lensans.pushbacki; } 構造解 int cur = 0; for int i = len; i = 1; i-- { 依照字典序做 sort sortalllensi, cmp; for auto j : lensi { 排除在目前選到的元素左邊的元素 if j = cur continue; 排除加入後會相交的元素 用於排除文章中寫的“一個小測資”那段的 Case if vj vcur continue; cur = j; 把 index 映射回去並輸出 cout rposvj " "; break; } }}

TIOJ

題解 CSES Restaurant Customers

給你 n 位客人的進入和離開餐廳的時間 輸出最多同時有幾位客人同時在餐廳- n le 2 times 10^5把每個人加入時間和離開的時間分別看成兩個時間點 並把所有時間點加入陣列後一起排序 然後用一個變數來維護目前餐廳人數 每次遇到加入就增加 反之遇到離開就減少 維護中遇到的最大值就是答案了 時間複雜度:Oncpp using namespace std; signed main { int n; cin n; vectorpii v; for int i = 0; i n; i++ { int s, t; cin s t; v.pushback{s, true}; v.pushback{t, false}; } sortv.begin, v.end; int cur = 0; int ans = 0; for auto e : v { if e.ss == true cur++; else cur--; ans = maxcur, ans; } cout ans endl;}

CSES

題解 CSES Repetitions

你有一個由 A、C、G、T 組成的字串 目標是算出同樣的字母最多連續重複幾次把整個字串從左邊往右掃 用一個 curLen 變數維護目前的長度 遇到一個字母時 curLen 加 1 如果跟上個字母不同就把 curLen 歸零 每次掃過一個字母再用 maxLen 維護出現過最大的 curLencppusing namespace std;signed main { char chr, tmp = 'X'; int maxLen = 1, curLen = 1; while cin chr { if tmp = 'X' tmp == chr { curLen++; } else { curLen = 1; } maxLen = maxmaxLen, curLen; tmp = chr; } cout maxLen endl;}

CSES