SCOI 2024

日期:
标签: journal

已經連續寫了好多篇遊記了,博客不知道該寫什麼好了。


Day -

省選前最後一場模擬賽。教練專門組織我們去了初中校區考試,說是要模擬真實環境。本來是信心賽,結果 T1 就做了兩個半小時多,只有 120,墊了底。考完教練請我們去校外的李莊白肉喫了頓飯,也是教練第一次請我們喫飯。

Day 1

考場是電子科大,來過幾次了,但是省選安排的比較寒酸,連個志願者都沒有,也沒有路標指引,跟着人羣走,聽說還有走到隔壁雅思考場的。

機子相當奇怪,字體渲染沒有抗鋸齒,安裝有騰訊殺毒,VS Code 不能用,不過我在虛擬機下寫代碼,體驗還行。鍵盤不是傳說的那種 backspace 非常小的,比較適應。監考老師挺煩人的,每隔一段時間就要提醒“不要碰到電源線了”。希望能早日像 WC 或國賽那樣直接上 Linux 實體機,再配備 SelfEval。虛擬機太垃了。

SCOI Day1 的题目:

  1. 給定長度爲 n 的字符串數組 s 和長度爲 m 的字符串數組 t,求 sum i sum j sum k sum l f(i, j, k, l),其中 f(i, j, k, l) 表示 si+tj 在 sk+tl 中的出現次數。

  2. 給定 n 個點及一個矩形,令 Di(P) 表示 P 到第 i 個點的歐幾里得距離,對於每一對 (i,j) 求滿足恰好有 j 個 k 滿足 Dk(P) < Di(P) 的 P 的面積。

  3. 有 n 個二元組 (ai, bi),如果某个时刻某个ai 小於等於 0,則会被刪除,并让所有未删除的二元组的 aj -= bi。每次操作可以让某个 ai 变成 0,问最少多少次操作才能将二元组删完。但是不給定 b,給定每个 bi 的范围 li <= bi <= ri,问所有 b 取值中上面问题的答案的和。

先是先掃了一眼所有題目,T1 顯然是最可做的,不久想出了了做法。比較幸運,考前字符串啥都沒複習,就唯獨瞥了一眼 AC 自動機的板子。然而這個東西竟然花了我兩個多小時都沒調出來,第二個較大樣例的過不去,gdb 輸出 std:: vector 也有時靈有時不靈的,調試非常惱火,急了。部分分還一點沒打,只好趕緊看看後面兩題的暴力。

T2 要求算面積,沒啥好寫的部分分,不得不先跳過。T3 就連確定 b 的問題我都只會 的做法,寫了最低檔的暴力,放棄了。再回頭看 T1,幸運的是,不久就過了大樣例,結果一拍,又出了鍋,大樣例弱的離譜。慌啊。好在這個錯誤,調試思路比較明確, gdb 也沒抽風,在最後還剩一個小時的時候終於調了出來。相當激動,8K 的代碼啊,看看周圍好像也沒幾個寫出 T1 的,自信起來了。

最後打算看看 T2 暴力。好像沒有什麼好寫的,我能想到的暴力就是求出每對點的中垂線,然後再算出中垂線分割的每個部分的面積,非常難寫,這麼點時間肯定寫不出來。有一個共圓的部分分,寫了 5K 代碼,最後還剩下 10min 才寫完,樣例也來不及測了,由於輸出浮點數,來不及寫 spj,看了下最小的樣例,好像是對的。然後就關掉虛擬機,整理下文件夾,結束了。

後來想想,如果 T1 沒調出來,我連 T1 性質部分分都來不及寫,只能 40 遺憾離場,挺恐怖的,不過還好調出來了。平時大一點的題目少有在這麼短時間做出來的,練習太少了,做起來很慌,把握不好時間。

Day 2

題目:

  1. 給定 n 個數字串,每次操作交換兩個不同位置,問所有交換方案的數字串的值的積的和(允許前導零)。
  2. 給定 n x m 的網格圖,邊有邊權,問至少刪除幾條邊纔不存在從 (1,1) 到 (n,m) 的路經滿足路經 gcd 大於 1。需要支持修改某條邊權等於 1 的邊的邊權,強制在線。
  3. 給定 n x m 的網格圖,在上面擺放如:
|_ |  |__
   |_

這樣的總共 12 種 L 形塊。要求每一條網格邊都被覆蓋且僅覆蓋一次。構造方案滿足使用的 L 數量最少。

開考看到 T1 完全沒思路,先打了個暴力,結果測了下極限數據,要跑 2s 多,怎麼 10pts 暴力都要卡常,出題人太可惡。然後看部分分,想 N=1 的,想出來的做法手算總是答案不對,而且總是要枚舉 K,折騰一個多小時後,就放棄了。感覺狀態不好,很急。

看看 T2,想到判定是否有路經可以枚舉質因子然後判連通性,但是判定一次都要 O(nm) 了,而且如果答案是 1 或者 2 需要判定 O(nm) 次,所以果斷放棄。但是暴力也寫的很不順利,腦癱了枚舉了所有邊的所有因子,不過區別其實不大。然後調試的時候遇到使用 std::vector<bool> address sanitizer 報錯,但是 std::vector<int> 就不報錯的情況,而且 gdb 也時不時抽風,應該是 RE 了沒判出來。排查了半天發現是非強制在線的點忘記將 ij 減一了(爲什麼大家都不喜歡從 0 開始編號啊)。老版本 gdb 和 sanitizer 太難用了。

T3 構造,感覺很不可做,先把 min(n,m)=1 的部分分做了,還是比較簡單,結果 checker 告訴我答案出界。最終發現是題目要求 n columns m rows,非常傻逼。嘗試衝 min(n,m)=2 構造了半天不會,沒腦子。

到頭來發現自己只有 30pts,挺慌,再想想 T1 部分分。有個 k=1 的好像比較好做,但是要推式子,一堆 Σ 亂七八糟的。中途去上了一次廁所,回來把電源線踢掉了。重啓浪費了快十分鐘,uestc 機房太垃了。好在式子推出來了,手造了幾個樣例,沒啥問題。然後就不知道怎麼做了,45pts 也就是墊底水平,心灰意冷地關掉了虛擬機。最後還剩五分鐘的時候突然想起有 T2 有個 q=0 的部分分,於是趕忙用 devc++ 打開程序,加了個輸出 0 的代碼。

進隊徹底是沒希望了,中午出去後和 xy 和 wcx 喫飯,中途出了成績,xy T3 竟然有 70pts,而我 T1 不知爲何只有 10pts。和同桌喫飯的兩個同學就被區分開了,感到悲傷。又想起了 WC 的慘痛經歷,想起坐在鐵牌區看着一個個熟悉同學去上臺領獎。

不過倘若我進了省隊,以我的水平,參加 NOI 或許也只能打個銅牌,水平差是事實。補一補文化課也好,畢竟我確實是沒能力拿金牌的,最終宿命都是高考。來年再戰。