最後更新日期 2024 / 01 / 01
TOI 新手同好會心得文
前往師大
有點怕遲到很早出門
結果正式開始前半小時就到師大了
不過教室已經開了
就到裡面坐著寫寫題
等工作人員準備一下之後
很快就開放參與者報到了
領了名牌還有幾個師大的紀念品
因為下午團體賽要分組所以也抽了組別的籤
個人賽
比賽時常 2.5 小時總共有 8 題
開賽後先打開了第一題
但看到一堆複雜的算式所以就先跳過了
第二題感覺就是排序裸題
但沒看很仔細導致看不懂題目所以也跳過了
第三題是字串模擬題
我決定從這題開始下手
結果因為最近用 Mac 而且家裡 Windowns 鍵盤跟比賽的差很多的關係
打字打的超痛苦
方向鍵位置差很多而且要按 ctrl 一直按到 alt
寫到心態很崩
這種水題傳上去甚至還吃了一個 WA
我甚至在想為什麼我要花時間來這裡受苦受難
重新看題目後發現原來完全理解錯意思了
修改一下之後總算 AC 了一題 \
翻開第四題
看到測資範圍到了
總算看到一題算法題了
大概花幾分鐘思考就把雙指針寫完
不過還是吃了幾次 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;}
CSESCodeforces 918 Div 4 題解
為了慶祝第一次在 CF 破台所以難得來寫一下題解 這成績我可以開心一個禮拜了 : ~~然後今天早上過的太廢一題都沒寫不知道是不是因為這樣把能量都留到這場釋放了~~給定三個數，其中兩個數相同，找到不同的那一個數直接照題意模擬做就行了，實作的部分用 map 很方便cppusing namespace std; int main { int t, tmp; cin t; while t-- { mapint, int cnt; 計算每個數字出現幾次 for int i = 1; i = 3; i++ { cin tmp; cnttmp++; } 找到出現次數為 1 的那個數 for auto num, frq : cnt { if frq == 1 cout num endl; } }}給予一個 3x3 的矩陣，每行、列都剛好包含各一個 A、B、C 字母，但某一格未知，任務是找到未知的那格是什麼直接照題意模擬做就行了，實作的部分用 set 很方便cppusing namespace std;char tb55; 檢查矩陣是否合法bool check { 檢查每個 row for int i = 0; i 3; i++ { setchar st; for int j = 0; j 3; j++ { st.inserttbij; } if st.size = 3 return false; } 檢查每個 column for int i = 0; i 3; i++ { setchar st; for int j = 0; j 3; j++ { st.inserttbji; } if st.size = 3 return false; } return true;}int main { int t; cin t; while t-- { int px, py; 未知格的座標 for int i = 0; i 3; i++ { for int j = 0; j 3; j++ { cin tbij; if tbij == '?' { px = i; py = j; } } } 枚舉該放哪個字母 for char c = 'A'; c = 'C'; c++ { tbpxpy = c; 如果合法就輸出 if check { cout c endl; } } }}有 n 個盒子，第 i 個盒子裝著 ai 個 1x1 的紙片，求是否可以剛好用所有的紙片拼成一個平片的正方形？事實上題目問的就只是 sum{i=1}^n ai 是否為完全平方數 所以只需要加總後開根在平方看是否跟原始的數相等就行了cppusing namespace std;signed main { int t; cin t; while t-- { int n, tmp, sum = 0; cin n; for int i = 0; i n; i++ { cin tmp; sum += tmp; } if squareintsqrtsum == sum { cout "YES" endl; } else { cout "NO" endl; } }}有一種只包含 a、b、c、d、e 的語言，這些字母被分成兩種類型- Vowels — 包含字母 a 和 e，用 V 表示- Consonants — 包含字母 b、c、d，用 C 表示一個合法的段落可能為 CV 或 CVC 給予一串文字 求將它按照規則分段的結果直接隨便取的話會出一些問題 不過其實只需要觀察到兩個 C 不能連再一起就完事了 雖然我也還沒完整的證過 因為我不是數學家cppusing namespace std; 儲存每個字母是 v 或 c 類mapchar, char tb = { {'a', 'v'}, {'b', 'c'}, {'c', 'c'}, {'d', 'c'}, {'e', 'v'},};void sol { int n; string s; 題目給的字串 string ss; 轉換過後只包含 c 跟 v 的字串 cin n s; 轉換字串 for auto c : s ss += tbc; 分段後的結果 vectorstring ans; for int i = 0; i s.size; { if i == s.size - 3 { 只剩下最後三個字就直接全取 ans.pushbacks.substri, 3; break; } if ssi+3 == ssi+2 ssi+2 == 'c' { 如果選 CV 會導致兩個連續 C 的情況出現就改選 CVC ans.pushbacks.substri, 3; i = i + 3; } else { 否則就選 CV ans.pushbacks.substri, 2; i = i + 2; } } 輸出解 for int i = 0; i ans.size; i++ { if i = 0 cout "."; cout ansi; } cout endl;} int main { int t; cin t; while t-- sol;}給定一個陣列，求是否存在一段連續的區間滿足偶數 index 的所有元素加起來等於奇數 index 的元素把偶數 index 的元素都加上負號再套上前綴和之後 題目就被轉換成找到一個區間滿足總和為 0也就是說只要從左掃到右 並對於每個位置檢查左邊是否存在相同值的元素即可cppusing namespace std; void sol { int n; cin n; vectorint an; for int i = 0; i n; i++ { cin ai; if i % 2 == 0 ai = -1; } vectorint psumn + 1; partialsuma.begin, a.end, psum.begin + 1; setint st; for auto e : psum { if st.finde = st.end { cout "YES" endl; return; } st.inserte; } cout "NO" endl;} signed main { int t; cin t; while t-- sol;}有 n 個人在數線上以每秒 1 格的速度往右走，第 i 個人的起點為 ai 終點為 bi，求他們倆倆碰面（同時出現在同一格）的次數仔細觀察之後會發現 只有 ai aj 且 bi bj 的情況下 i 跟 j 才會碰面 也就是一個區間把另外一個區間包住的情況可以發現其實就跟 CSES 的 Nested Ranges Count 完全一樣 那這題網路上題解很多 算法細節就不多提了cppusing namespace std;using namespace gnupbds;template class T using orderedset = treeT, nulltype, lessT, rbtreetag, treeorderstatisticsnodeupdate;void sol { int n; cin n; vectorint beconn, yidxn; vectortupleint, int, int bn, cn; for int i = 0; i n; ++i { int l, r; cin l r; bi = {l, r -1, i}; ci = {r, l -1, i}; } sortb.begin, b.end; sortc.begin, c.end; for int i = 0; i n; ++i yidxget2bi = i; orderedsetint s; for int i = 0; i n; ++i { int idx = get2ci; int cur = yidxidx; beconidx = s.size - s.orderofkeycur; s.insertcur; } int ans = 0; for int i = 0; i n; ++i ans += beconi; cout ans endl;} signed main { io; int t; cin t; while t-- sol;}給一張無向帶權圖，第 i 條邊連接著 vi 及 ui 且權重為 wi，你可以在節點 i 拿到一台速度為 si 的腳踏車，騎著速度為 si 的腳踏車經過第 j 條邊時需要花費 si times wj，求全程騎腳踏車從 1 走到 n 的最少時間花費不難想到從點 v 獲得腳踏車後到其他每個點 u 的最少時間花費為 distv, u sv 其中 dist 代表兩點最短路徑長度 那其實就只要依照上面的規則把那些邊都建在新的圖上 最後對新的圖做最短路就可以了補充資料: 最短路演算法cppusing namespace std;const int maxn = 1e3 + 10;const int inf = 1e13; int n, m;vectorpii gmaxn;int bikemaxn; vectorpii g2maxn;int dist2maxnmaxn; int distmaxn; void sol { 初始化 讀取輸入 cin n m; for int i = 0; i = n; i++ { for int j = 0; j = n; j++ { dist2ij = inf; } } for int i = 0; i = n; i++ { gi.clear; g2i.clear; } for int i = 0; i m; i++ { int a, b, w; cin a b w; ga.pushback{b, w}; gb.pushback{a, w}; } for int i = 1; i = n; i++ { cin bikei; } 在原始的圖上求每個點對得最短路 for int v = 1; v = n; v++ { 初始化 for int i = 1; i = n; i++ { disti = inf; } 使用 dijkstra 演算法 priorityqueuepii, vectorpii, greaterpii pq; pq.push{0, v}; distv = 0; while pq.size { auto now = pq.top; pq.pop; if now.ff distnow.ss continue; for auto other : gnow.ss { if distother.ff distnow.ss + other.ss { distother.ff = distnow.ss + other.ss; pq.push{distother.ff, other.ff}; } } } 建邊在新的圖上 for int i = 1; i = n; i++ { if i == v continue; g2v.pushback{i, disti bikev}; } } 初始化 準備在新的圖上做最短路 for int i = 1; i = n; i++ { disti = inf; } 使用 dijkstra 演算法 priorityqueuepii, vectorpii, greaterpii pq; pq.push{0, 1}; dist1 = 0; while pq.size { auto now = pq.top; pq.pop; if now.ff distnow.ss continue; for auto other : g2now.ss { if distother.ff distnow.ss + other.ss { distother.ff = distnow.ss + other.ss; pq.push{distother.ff, other.ff}; } } } 輸出解 cout distn endl;} signed main { int t; cin t; while t-- sol;}
Codeforces