2024-01-25
和 wcx、xy 和 lzq 坐火車去重慶。在火車上非常無聊，我們先一起玩了（復古的）水果忍者，然後又玩了會兒 Hypixel 和 Reaching Darkness，但網絡實在難受，便放棄了。最後只好玩些單機的，玩了 pvz 和 Getaway Shootout。驚喜地發現 Getaway Shootout 出了新的速通模式。
來到重慶，確實地感受到重慶地形崎嶇，坐出租車去酒店，一會兒上一會兒下，到處都是天橋、地下通道，非常混亂，跟着導航也不容易找到路。可能是天氣原因，看起來灰濛濛的。
中午去喫了羊肉。
發現忘帶機械鍵盤要用的 type-c to usb 接口，也沒帶耳機，憤怒。
晚上去 Library Checker 上打了打板子，雖然明知道大概率沒用（
2024-01-26 (Day 1)
地點是在重慶市育才中學。重慶育才中學環境非常好，風景很美觀，教學樓甚至有電梯。
上午先放了進一個小時育才的宣傳片（徵得我好像會去這個中學一樣），然後又有北大的陆院長講話，不過陆院長講話脫稿好評。介紹北大的時候，陆院長放了一張 CSRankings 的圖片，是北大 rank 1，結果我們下頭自己查發現是清華第一（
然後就是合影和試機。試機的時候試機題是 PKUSC2021 的 Day1 T1 Sum Transformation，結果做了一個小時沒做出來。還發現裝得那個 vim 沒有 +clipboard，不能粘到系統剪貼板，交代碼又不能提交文件，很難受。而且試機早知道應該打一個 static_modint 之類實用一點的東西，經驗太缺乏了。
午餐非常豐盛！有八個菜隨便選，還有草莓、橘子和飲料。
然後就是正賽了。
題目：
- 給定一個長度爲 n 的 LR 序列 S，Alice 和 Bob 輪流在這個序列上操作，每次選擇一個下標 i，如果 Si=L，則保留 i 左側的，否則保留 i 右側的。當 S 爲空的時候失敗，問 Alice 和 Bob 誰必勝。
- 有一個長度爲 n-1 的數組 f，令 f’i 表示所有左/右端點是 i 的區間的最小值之和，給定 f’，構造一個對應的 f（不保證有解）。
- 給定一個大根二叉堆，每次操作選定一個位置變成 0，然後將這個位置向下交換使得堆的性質仍然滿足。令 f(S) 表示將這個二叉堆進行若干次上面操作後，S 內的所有位置不爲 0，且二叉堆和最小的堆（是唯一的）。多次詢問，有兩個集合 S1,S2，問有多少 S1 ⊆ S ⊆ S1 ∪ S2，滿足 f(S) 的 x 位置的值是 z。
第一個問題比較簡單，我 20 多分鐘就過了，感覺非常自信。然後想 T2，一開始往高斯消元那邊想，但是衝了好久也沒啥進展。於是去看 T3，發現完全不可做，猜了一個結論然後試着去寫了一下，結果是對的，於是拿到了 40 暴力，果斷放棄 T3。繼續衝 T2，先做了一個 11 的最低檔暴力，然後嘗試 15 分的 n <= 8，在最後半個多小時的時候發現了一個非常有用的性質，結果寫完沒調出來。最後 100+11+40，大衆分。
ssz 考了 100+26+40，把 T2 的那個 n <= 8 做出來了，orz。但是 hfy 只考了 111。
晚餐去喫烤鴨和火鍋。
晚上和 lzq 一起玩去南京集訓時玩的 Random Royale，可惜 xy 沒下好 Minecraft，要不然還能多一個人。
2024-01-27 (Day 2)
早上看到了 cyb 發來的鼓勵視頻，陈老居然還記得我們，感動。
上午聽了北大王迪教授的講座，講編程語言，感覺很牛的樣子。
附上 Day 2 午餐的圖片，Day 1 忘記拍照了：
下午比賽，題目：
- 給定一個包含若干實數的可重集 S，每次操作可以讓一個元素四捨五入，或將兩個元素相加，問最後集合的和最大是多少。
- 問有多少個排列，進行 shell sort，可以讓交換次數最大。求出最大交換次數和排列數量。
- 有 n 個棧，需要支持一下三個操作：(1) 區間 [l, r] 的所有棧壓入 x 個 y；(2) 區間 [l, r] 的所有棧彈出 x 個元素；(3) 查詢第 k 個棧 [p, q] 的元素和。
感覺 T1 就相當困難啊，首先想到小數部分 ≥ .5 的可以直接四捨五入，爲 0 的可以直接忽略，只剩下小數部分爲 .1, .2, .3 和 .4 的。然後就想了半個多小時，沒有什麼進展，於是準備先打點部分分。先寫了 T1 O(n^4) 暴力，結果 TLE 了兩個很小的 subtask，然後又卡了卡常數過了。接下來先看 T2 T3，感覺都巨大困難，於是打個暴力就跑路了。
繼續來看 T1，有看到有個都是 .2 倍數的部分分，感覺沒什麼頭緒，直到我嘗試寫了一個這樣的東西：
def calc24(i, j):
return [k + (i - k) // 3 + (j - k) // 2 for i in range(min(i, j) + 1)]
即枚舉 .2+.4 一組的數量，然後剩下的單獨組。這個東西不是單調的，但是好像最後最後一個元素是最大值？然後就寫了一個程序就過了那個部分分？！
繼續衝 T1，想到可以通過調整使得儘量多組 .1+.4 和 .2+.3，這樣最多剩下兩個數。通過類似上面的方法，發現如果剩下 (.3,.4), (.2,.4), (.1,.3) 都有這樣的性質，可以直接 O(1) 做。但是 (.1,.2) 卻沒有這樣的性質，而且有 .1*5, .1*3 + .2, .1 + .2*2, .2*3 四種組合，非常不好處理。最後我決定枚舉 .1 * 3 + .2 的數量，然後有倒着枚舉 100 個 .1 + .2 * 2 的數量（因爲有向下取整，這個和餘數有關），結果就過了。此時還有 1h。
然後發現 T2 可以狀壓，又多了 27 分，再看剩下的沒啥時間做了，就開始玩耍 emacs 上的貪喫蛇。
最後出來，大家 Day 2 分都差不多，但是 hfy Day 2 270，直接翻盤，orz。