PKUWC 2024

日期:
标签: journal

2024-01-25

和 wcx、xy 和 lzq 坐火車去重慶。在火車上非常無聊,我們先一起玩了(復古的)水果忍者,然後又玩了會兒 Hypixel 和 Reaching Darkness,但網絡實在難受,便放棄了。最後只好玩些單機的,玩了 pvz 和 Getaway Shootout。驚喜地發現 Getaway Shootout 出了新的速通模式。

arrive at cqbz

來到重慶,確實地感受到重慶地形崎嶇,坐出租車去酒店,一會兒上一會兒下,到處都是天橋、地下通道,非常混亂,跟着導航也不容易找到路。可能是天氣原因,看起來灰濛濛的。

中午去喫了羊肉。

發現忘帶機械鍵盤要用的 type-c to usb 接口,也沒帶耳機,憤怒。

晚上去 Library Checker 上打了打板子,雖然明知道大概率沒用(

2024-01-26 (Day 1)

地點是在重慶市育才中學。重慶育才中學環境非常好,風景很美觀,教學樓甚至有電梯。

上午先放了進一個小時育才的宣傳片(徵得我好像會去這個中學一樣),然後又有北大的陆院長講話,不過陆院長講話脫稿好評。介紹北大的時候,陆院長放了一張 CSRankings 的圖片,是北大 rank 1,結果我們下頭自己查發現是清華第一(

然後就是合影和試機。試機的時候試機題是 PKUSC2021 的 Day1 T1 Sum Transformation,結果做了一個小時沒做出來。還發現裝得那個 vim 沒有 +clipboard,不能粘到系統剪貼板,交代碼又不能提交文件,很難受。而且試機早知道應該打一個 static_modint 之類實用一點的東西,經驗太缺乏了。

午餐非常豐盛!有八個菜隨便選,還有草莓、橘子和飲料。

然後就是正賽了。

competition location

題目:

  1. 給定一個長度爲 n 的 LR 序列 S,Alice 和 Bob 輪流在這個序列上操作,每次選擇一個下標 i,如果 Si=L,則保留 i 左側的,否則保留 i 右側的。當 S 爲空的時候失敗,問 Alice 和 Bob 誰必勝。
  2. 有一個長度爲 n-1 的數組 f,令 f’i 表示所有左/右端點是 i 的區間的最小值之和,給定 f’,構造一個對應的 f(不保證有解)。
  3. 給定一個大根二叉堆,每次操作選定一個位置變成 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。

晚餐去喫烤鴨和火鍋。

eating hotpot

晚上和 lzq 一起玩去南京集訓時玩的 Random Royale,可惜 xy 沒下好 Minecraft,要不然還能多一個人。

2024-01-27 (Day 2)

早上看到了 cyb 發來的鼓勵視頻,陈老居然還記得我們,感動。

上午聽了北大王迪教授的講座,講編程語言,感覺很牛的樣子。

附上 Day 2 午餐的圖片,Day 1 忘記拍照了:

lunch

下午比賽,題目:

  1. 給定一個包含若干實數的可重集 S,每次操作可以讓一個元素四捨五入,或將兩個元素相加,問最後集合的和最大是多少。
  2. 問有多少個排列,進行 shell sort,可以讓交換次數最大。求出最大交換次數和排列數量。
  3. 有 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。