[TOI] 2022 2 模 + 1! 心得

,

前言

長話短說，我沒有進 2!，Rk. 14 w/ -41.0
結果是，如果我一模過了 A 48 或 C，就會進二階。
我不知道接下來要怎麼辦，
但至少把現在的想法記錄下來，之後再回來看，或明年的這時候再回來看，
或許會有不一樣的感覺吧，
又或者到了那個時候，我比今年還更慘。

接下來的內容可能有點負面，請自行斟酌閱讀。

1! 總結

基本上跟去年類似，資奧真的是一個很歡樂的地方，
比起去年而言，我跟其他人更熟了一點~~，也多噴了很多怪話~~
每天的日程大概是聽課／寫題／vir OI → 午餐 → 聽課／寫題／vir 剛剛暫停的 OI → 晚餐 → 耍廢 → 回飯店打日麻
高一的時候真的不知道在幹嘛，今年至少比較有進入狀況了。
一些酷／怪事：

  • 球場都在整修沒辦法打球 qwq
  • TIOJ 愚人節比賽（對不起 A 爆雷的那個就是我，我道歉 qwq）
  • 剛打開就有預處理的拼圖
  • 連續兩次延期的模考
  • PixelCat 被我盜帳超多次
  • 友人場三人南和出國士無雙，但還是吃三位
  • 變超好的西餐廳（但是很貴 qwq）
  • shaun 的國士無雙 orz
  • 看到附中高一都在刷 USACO Guide Platinum 但我還在 Silver qwq 這項真的不是我裝弱，我 Silver 裡面有很多 Very Hard 跟 Insane 都寫不出來
  • 我怪話 Rk. 1
  • 學會用 vim

2 模

註：以下很多是靠印象的，所以沒有實際時間，甚至順序我可能記錯了，
所以僅供參考而已。

開場先登入跟打 .vimrc，
然後先讀了 A

  • A roller [1.0s, 1 GB]
    給你 $n$ 個點的樹，有 $m$ 個點有不同的油漆滾筒，油漆滾筒可以自由的在同色的地方移動，如果移動到空白就會把那格染上那個顏色，另外不能移動到已經被塗色的地方。
    定義兩個方案不同若且唯若按照被染色的順序排列空白節點之後，存在一個位置兩個方案的節點不同或染的顏色不同，輸出方案數 $\mod 10^9 + 7$。
    $1 \leq m \leq n \leq 500$
    [7] $n \leq 8$
    [25] $n \leq 20$
    [29] 每個點的點度至多是 $3$
    [39] 無額外限制

看了覺得是樹 DP，但怎麼推卻發現狀態越開越多，亂做做到還要一堆數學式子就覺得他是難題就先放著了。

  • B fertility [Communication, 5.0s, 1 GB]
    Judge 有一個 $n \times n$ 的 +1/-1 網格，
    你可以詢問一格或一個矩形的總和最多 $40000$ 次，決定一條從 $(0,\,0)$ 到 $(n,\,n)$ 只包含 U、R 的路徑，
    如果你的詢問跟路徑都是合法的，則答案的價值 $a$ 定義為這條路徑右下的總和。若最佳解為 $a^*$，則你的分數 $S$ 被定義為
    $S = \begin{cases} 0.0 & a < 0 \\ 1.0 & a > 0.99a^* \\ \frac{a}{0.99a^*} & \text{otherwise} \end{cases}$
    $3 \leq n \leq 1000 ,\, a^* \geq 2n$
    [11] $n \leq 100$
    [14] 每個列的值非嚴格遞增
    [75] 無額外限制

剛看到大概就決定把他先丟掉了，只有知道 Subtask 1, 2 是可以確定性的做出來的。

  • C lantern [0.5s, 1 GB]
    給你 $4n$ 個數字 $c_i \in [0,\,n - 1]$ 以及評分常數 $k$，你要拿出 $2n$ 個數字使得所有 $c_i$ 都出現兩次，而且所選擇位置的總和恰好是全部的一半，接下來你要把他們兩兩配對，定義 $d$ 為位置總和最大那組及最小那組的差。有解輸出方案，無解請輸出 -1。
    你的分數 $S$ 定義為 $S = \begin{cases} 1.0 & \text{the test case don’t have any solution and you outputs } -1 \\ 0.0 & \text{the test case has a solution and you outputs } -1 \\ \dfrac{k}{k + d^{0.7}} & \text{otherwise} \end{cases}$ $1 \leq n \leq 10^5,\, 1 \leq k \leq 50$
    [10] $n \leq 10,\,k = 10$
    [31] $n \leq 210,\,k = 24$
    [59] 無額外限制

看到的第一想法是大怪題，甚至我猜根本沒有滿分解，就先丟掉等到後來再回來做好了。

  • D rectangle [0.5s, 1 GB]
    給你 $N$ 個矩形，第 $i$ 個個矩形有參數高 $H_i$、寬 $W_i$、亮度 $D_i$、成本參數 $C_i,\,F_i$。
    其中 $H$ 是單調遞增的，覆蓋 $[L,\,R]$ 的矩形需要成本 $$C_R \frac{\sum_{i = L}^{R}D_iW_i}{\sum_{i = L}^{R}W_i}\sum_{i = L}^{R}W_i + F_R$$
    問最小覆蓋成本。
    $1 \leq N \leq 2 \times 10^5,\, 1 \leq W_i,\,H_i \leq 10^6,\, -16 \leq D_i \leq 16,\, -10^6 \leq C_i,\, F_i \leq 10^6$
    [3] $N \leq 100$
    [8] $N \leq 2000$
    [12] $C_i = 1$
    [32] $D_i > 0$
    [45] 無額外限制

剛看到這題的時候感覺連 $O(N^2)$ 都只給 11 分是什麼狠題，但仔細一看才發現這題根本是裸的斜率優化，因為前面都太難所以二話不說直接開刻。

D 0

$\newline$

debug 了好多次都 WA，我記得這時候我大概花了一個多小時，但我覺得其他題目不好做，所以就決定寫暴力對拍看看，反正暴力很快，

D 0

$\newline$

？？？？？
確定轉移式是好的之後，就打算先放著去看看 A 有沒有好做法了。
推一推發現真的很難 DP，不限制時間下還是很難列出多項式時間的做法，
但就在我放棄 D 的 10 分鐘後，

D 測資有誤，稍後修正後將會進行 rejudge。

我看到之後心態簡直是崩了，等他 rejudge 完之後我還是 0 分，
但我覺得怪怪的，所以我就再傳了一次暴力（我印象中是傳完全一模一樣的 code），

D 11

$\newline$

？？？？？ 現在想起來我很有可能是傳到錯的 code，但印象中又沒有，

總之當下的心情蠻生氣的，
至少我對拍一下就抓到 bug 了，終於

D 100

$\newline$

這大概是第一次在模考裡面拿到 AC 吧，所以當下心態就直接回來了。

之後就繼續去推 A 的式子發現越推這坨東西根本就沒辦法推進到滿分，就決定先寫個快速的暴力

A 32

$\newline$

之後就去寫了 C 的暴力 $6^n$ 但 TLE，明明我覺得夠快，

至少好好實作把 B 的前兩個寫掉了，
這部分我就不細做說明，因為過程其實就蠻單純的，

B 25

$\newline$

後來發現自己 A 的解其實可以多做那 29，但越推越發現 case 很多而且數學的部分還要推，
所以就決定放棄去喇 B 跟 C，

首先是先在 C 的爆搜加了時間剪枝跟答案 0 剪枝，傳上去拿到

因應 D 測資問題，部分參賽者將延長比賽時間

調整的規則是（rejudge 前最後一次 submit 時間 - rejudge 前第一次分數有變動的 submission），
也就是說，儘管測資爛掉我還是沒補到時間，
有點想確認我的那個暴力到底是發生什麼事，
如果我沒想錯的話，我的時間是被吃掉了。

師大燒雞= =

C 6.66

$\newline$

然後就去把 B 的大子題打算用分塊做看看，但很不幸地沒有拿到任何分數。
這時候敗筆是，B 的難度顯然比 C 簡單，所以我應該隨便做 C 就回來做 B，

後來把 C 加了一些 random 喇到

C 8.23

然後比賽就結束了。

Result

Sum
A 7 25 29 39 32
B 11 14 75 25
C 8.23/10 31 59 8.23
D 3 8 12 32 45 100
Score 165.23

一二模 Rk. 14, 距 2! 線 -41

出場

出場大概知道自己涼了，沒有發現 B 其實可以亂喇喇到很高，
然後 C 聽到竟然是 2020 IMO p3 直接照抄，
我覺得師大今年真的是燒雞，
初選出了 2022、一模卡常、二模抄題目跟測資出爛，
接下來三四模又會長怎樣呢？

結果是，如果我一模過了 A 48 或 C，就會進二階。

檢討

這場我覺得時間安排上沒有很大的問題，但就是 B 我沒有好好喇，然後 C 我覺得我可能有機會猜出來吧（雖然機會渺茫），
總之今年就結果來講，我花了一年卻沒有什麼長進。

結訓

坐上到北車的接駁車上，就只有我一個人，
就這樣結束了，我的眼淚默默地流下來，
我看著我被卡常的事實，
好像也不能改變什麼。

下一年就是高三了，除了普通的課業還有學測要顧，
在高二的時候我光是一般的課業就沒辦法兼顧競程了，
在高三這年，我還能繼續堅持下去嗎？
今天坐車的時候，我很確定我要搭哪班車、到哪裡，
但同樣是今天，我不知道接下來該怎麼做，
看著明年就是最後一年了，
我的高中就好像恍恍惚惚少了一半，
今年高一的人明年還有高二、高三，但我
是不是，只剩最後的機會了？

明年的這個時候，我會在哪裡？

總之等 USACO Open 出來的時候我應該會再寫一篇（因為那場是選訓營裡打的），
到時候等我的心情沉澱之後，再看我到時候怎麼想吧。