游記

很久之前

jxp玄學卡線THU和PKU都沒有進，默哀。
我校似乎只剩hyw神仙和我了啊……希望好運

12.19

晚上到了北京，住在熟悉的地方——中關新園。我大概在這里考過PKUSC2018和PKUSC2019.
來的飛機上還在瘋狂頹廢，吃棗藥丸。
感覺yyf巨佬出的樹剖交互好題非常有趣，于是去寫了一下。

12.20

上午瘋狂頹廢之余寫了一道簡單的DP題, 發現不會，看了題解。來PKUWC不會DP，吃棗藥丸。
下午瘋狂頹廢之余寫了一遍多項式exp板子，犯了一兩個錯誤，吃棗藥丸。

12.21 Day1

上午開幕式。
下午機試。
打開T1頓時慌了，看上去不會做？瞎轉化了一波，莫名其妙把題意轉化錯了，于是前一個小時就在自閉中度過了。
到了1.5h的時候還不會做，心態漸崩，決定敲個暴力。敲完了，我怎么過不了樣例？？？結果發現居然轉化錯題意了……gg
沒啥繼續想下去的心態，于是\(21\)分走人了，T2沒思路，于是去看T3.
顯然可以反演一下，然后枚舉約數，如果\(m=1\)的話就是單點加單點查詢？\(m\)比較大似乎可以按被修改的次數分塊？決定先去寫一發\(m=1\)
寫完了，誒我怎么又過不了樣例？？自閉了好久發現自己又想錯了（想得過于簡單了），反演枚舉約數之后還得倍數加倍數求和。。。
gg，那不爆炸，最后兩次Dirichlet前綴和\(43\)分走人了
還剩2h15min, 覺得自己已經基本涼了，可是除了剛T2之外別無選擇
第一反應是設\(f[l][r][i][k]\)表示\([l,r]\)這個區間\(i\)輪之后還剩\(k\)個集合完全在其內部的概率，顯然這個只和區間長度有關，\(O(n^3)\)
還剩1h30min, 還能優化嗎……
最后狗急跳墻一般，用了一些我自己都不知道為什么對的玄學方法搞成了\(O(n^2)\)
總得分: \(21+50+43=114\)

不知何時養成了出考場堵緊雙耳不和別人交流的習慣，可是還是從耳縫里冒進幾句話，大概都在說T2的50分好水之類的。嗯，看來是涼了。
問了下，似乎SD的人都有點發揮失誤，hyw \(21+29+43\), wzm \(21+18+43\), yamf考崩T2只有\(1\)分，默哀。
后來發現T2我的思路完全是錯的，怪不得別人都覺得水我卻費了九牛二虎之力。
依然是每次考完試都有的失落……我什么時候才能變強一點點呢……

12.22 Day2

上午面試。
面試老師1: “請介紹一下你自己？有什么興趣愛好？參加過什么OI比賽？”
我: “……三次NOIPtg省一，NOI Cu, 2018ICPC青島賽區Cu, 2019ICPC上海賽區Au”
老師: “哈哈哈你拿了那么長時間銅牌終于拿到金牌了” (達成目標: 被面試老師無情嘲諷)
面試老師2: “請介紹一下你自己？有什么興趣愛好？你知道哥德巴赫猜想嗎？你知道它為什么難嗎？”
我: “……”
面試老師3: “給你2min時間跟我說下你有什么優點。開始計時了，快點快點快點快點，快快快！”
我: 頓時嚇傻了，坐了2min一個字沒說
老師忍不住了: “怎么不說啊？你文化課成績怎么樣？應該很好吧？”
我: “嗯” (開始虛)
老師: “別光嗯，給我個具體的數，多少人里排第幾？”
woc嚇傻了！！！還真問文化課成績……我級部后一半說出來不是得涼？
我: “初中的時候一直是600人里的前6”(只看期末的話這倒不假), “高中的時候……也排得比較靠前” (跪求別問我高中排第幾！！)
老師: “哦好，(又問了一些別的問題)時間到了你回去吧”
orz!!!!!!!!! 嚇死了，還好沒問高中排第幾，撿回一條命！！

下午機試。
看了一遍題，沒有秒掉任何一道，但我卻有種感覺就是今天要全場AK，于是照著AK的策略去打
T1題意好復雜，T2看似比較有趣，先看T2吧
這顯然是棵樹對吧，然后隨機情況下樹高是\(O(\log n)\), 從\(l\)開始暴力爬樹高，遇到右兒子取個反處理一下就好，不過取反那里似乎有一些細節
想了想開始寫，大概1h的時候拿到了\(65\)分
繼續想正解，感覺可以把暴力跳樹高改成預處理一些奇怪的東西，發現是和\(\min(r,R)\)有關，于是分別處理兩個部分，分界點是LCA
寫完過了樣例，喜提\(0\)分。查錯半小時失敗，于是打了個對拍和\(65\)分程序拍，結果發現果然又是取反那一部分細節出錯了……qswl
交上去終于得到了\(100\)分，已經過了2h35min, 這已經遠遠落后于我的預想，心態大崩
難不成要被今天斷送了……趕緊開T1
讀懂了之后發現是個括號匹配，相當于最少改變多少個括號變成合法括號串，一個柿子大概就寫完了（似乎還要個RMQ）
交上去又WA了，算了半天發現自己柿子又推錯了……所以實際上很多時候代碼寫不對并不是代碼能力的問題，細節想假毀一生
3h45min的時候，終于A掉了T1
只差T3了，沖沖沖！！！
瞪了15min發現顯然無窮大邊只能割兩條，于是兩個點集分別是一段連續區間(這速度我也真是無fuck說)
然后先寫了個暴力統計每個區間的權值，然后\(O(n^2)\)求所有的答案，幾分鐘寫完了交上去，我特么怎么又WA0了？？！
查查查，這哪里有錯？數組開小？模數打錯？細節問題？？？查不出來改暴力，把兩部分都改成了\(O(n^4)\)的暴力，感覺還不夠暴力又改成了最最最暴力的暴力，可是始終連第一個Subtask都通不過！
時間僅剩30min, 面對一道我會的水題，我玄學錯誤只能拿\(0\)分，我能怎么辦！！我到底犯了什么錯！！我！！到底錯在哪？？！！
……
講個笑話：我讀入點之后對\(n\)取模來把\([1,n]\)變成\([0,n-1]\)

scanf("%d%d",&u,&v); v%=n;

……
無fuck說
還剩15min, 改過來，\(19\)分，又改成最初寫的那個，\(43\)分
改差分卡常就大功告成了！！！沖沖沖！！！還有13min來得及！！！
改完差分提交，然后去上了個廁所，“做好了回來卡常的準備”
上完回來，發現滿屏藍色，最大的點\(2400\ \text{ms}\)
看了一眼時鐘，剛剛好是17:50:00. 我以一種非常不體面的方式，在最后時刻，驚險地，AK了。(獲得成就: 達到全場平均分)
總得分: \(21+50+43+100+100+100=414\)
內心異常平靜，絲毫沒有什么喜悅之情，內心卻充滿了速度極度落后帶來的失落，開始腦補場面
2h的時候, 人均切前兩題，我卻面對著T2的\(0\)分不知所措，驚慌地打對拍
3h的時候, yamf,hyw,wzm,ldx,xlh等神仙已經AK了，而我還在面對著T1焦頭爛額……
4h的時候, 大批人員提前離場，沒離場的人也都AK了，我還剛剛拍著腦門意識到：哦，這每個連通塊是個連續區間啊！
4h40min, 我捶胸頓足，渾身顫抖，右邊的鎮海老哥大概會想: 這是哪來的骯臟下流又菜的sb？
4h50min, 我好不容易掙扎著從泥潭里走了出來，右邊的鎮海老哥悠閑地玩著鼠標，仿佛在不屑地嘲諷著我這個菜雞。
出了考場，只能面對早已離場的人們的無情嘲諷，像去年一樣強忍著淚水垂頭喪氣溜回酒店
等回了學校, jxp會問我要題，并用我六分之一的時間把它們秒掉；ckw&zyb要是看了題大概又會說: “這day1打到\(243\)不難吧？day2為啥3h AK不了？”
……

最后10min過去了，考試結束，懶得堵耳了，直接穿過人群走出考場，發現以上似乎并不真實
遇到hyw問我切了幾道，我有足夠的理由相信她AK了于是說“我差一點沒命啊”，沒想到她又笑著問我切了幾道，我嚇懵了，沒經過大腦說了一句“你沒有AK嗎？”她竟臉色突變，很吃驚地問我“你AK了？”我察覺到事情不對，問“蛤你哪個題沒過？”hyw:“T2T3都沒過，\(100+32+68=200\)”……
然后又在門口遇到了不少人，印象中的畫面就是: XXX出來，hyw問多少分，答二百多，hyw指著我說“他AK了”，然后又來下一個人，hyw繼續問，直到xlh出來說自己AK了才停下，搞得我非常懵逼地在門口站了兩分鐘
yamf \(200\)零幾，ldx \(268\), xlhAK(但他Day1似乎\(82\)?)
嚇傻了……這題是被集體降智了嗎……好多水平遠在我之上的人都考砸了……難受……
OI這個東西……真的太靠運氣了啊……

晚上和hyw一起被yhy學長帶著玩了一圈PKU，了解了一下他們現在的學習生活
上大學真累啊……不過我連大學都沒得上啊……
另外還聽說THU考了若干大數據結構，還好沒去THU……不然命都沒了……

12.23

上午頹廢。
下午頒獎。
PKU大概是擺明了不喜歡高二，yamf只拿了二等。SD好像還有女生wyx拿了二等。一等發得挺多，ldx一等，hyw和wzm一等，替他們感到高興。(srO wzm Orzzz 被初中學弟錘爆的恐懼！)
晚上回青島，準備上文化課——新一輪的自閉。
我這么菜，大概只能回去學文化課了吧。

一些感想

忽略結果來看，這次比賽還是暴露了我的各種弱點，并且我感覺到自己的水平再提升已經相當困難了。
現在政策很不樂觀，以后只能文化課OI兩手準備，今年爭取進入省隊拿到Ag, 然后很可能就得被迫離開OI這個四年以來一直給我欣喜給我動力給我失落給我打擊的良師益友了。
希望能化壓力為動力，珍惜最后的時間，放手一搏吧。
(本來這后面還寫了個感謝，想了想還是刪掉了……這種東西是不是退役的時候寫比較好啊，現在就默認自己要退役了未免過分了點)

題面整理

Day1 T1

給定一個\(1..n\)的排列\(p\), 定義\(L(p)\)為字典序不超過\(p\)的所有\(1..n\)的排列按字典序從小到大依次連接而成的序列。求\(L(p)\)本質不同的子序列個數，對\(998244353\)取模。
數據范圍: \(1\le n\le 50\)
Subtask1 (\(21\)pts): \(n\le 8\)
Subtask2 (\(47\)pts): \(\forall i, P_i=n-i+1\)
Subtask3 (\(32\)pts): 無特殊限制

Day1 T2

有\(n?\)個數\(a_i?\), 初始每個數構成一個集合。每次隨機選兩個集合合并成同一集合。定義一個局面的權值為當前所有集合最大值與最小值之差的平方和。定義\(f(k)?\)為合并到還剩下\(k?\)個集合時局面價值的期望。給定\(L,R?\), 求\(\sum^R_{i=L}f(k)^{97376}\)對\(998244353\)取模的值。
數據范圍: \(1\le n\le 2\times 10^5, 0\le a_i\lt 998244353\)
Subtask1 (\(1\)pts): \(L=R=1\)
Subtask2 (\(9\)pts): \(n\le 7\)
Subtask3 (\(8\)pts): \(L=R=n-1\)
Subtask4 (\(11\)pts): \(n\le 100\)
Subtask5 (\(21\)pts): \(n\le 2000\)
Subtask6 (\(13\)pts): \(L=R\)
Subtask7 (\(37\)pts): 無特殊限制

Day1 T3

有一個\(n\times m\)的矩陣，初始時均為\(0\). 首先有\(q_1\)次修改操作, 每次給定\(s,l,r,x\), 表示將所有滿足\(\gcd(i,s)=1\)且\(l\le j\le r\)的位置\((i,j)\)的值加上\(x\). 修改結束后有\(q_2\)次詢問操作, 每次給定\(s,l,r,x\), 求滿足\(\gcd(i,s)=1\)且\(l\le j\le r\)的位置\((i,j)\)的權值和對\(998244353\)取模后的值。
數據范圍: \(n,m,q_1\le 5\times 10^4,q_2\le 10^5\)
Subtask1 (\(6\)pts): \(n,m,q_1,q_2\le 100\)
Subtask2 (\(13\)pts): \(n,m,q_1,q_2\le 5000\)
Subtask3 (\(24\)pts): \(m=1\)
Subtask4 (\(27\)pts): \(n,m,q_1\le 3\times 10^4\)
Subtask5 (\(30\)pts): 無特殊限制

Day2 T1

在一個雙人對戰游戲中，己方有兩種兵，記作0,1, 對方有兩種兵，記作A,B. 己方的兵是有順序的，以一個01序列的形式給出。有\(q\)次詢問，每次給出\(x\)和\(k\), 己方可以進行\(k\)次攻擊，第\(i\)次攻擊可以指定對方的任意一個兵，使用己方第\(i\)個兵攻打之(若對方已經沒有兵，則己方贏得游戲，否則必須進行攻擊)。A型兵受到1型兵的攻擊會消失，受到0型兵的攻擊無效。B型兵受到任何兵攻擊都會變成A型兵。現在已知對方有\(x\)個A型兵，求在保證己方能贏得游戲（消滅對方所有兵）的情況下對方最多有多少個B型兵。若己方不可能贏得游戲，輸出\(-1\).
數據范圍: \(n,q\le 4\times 10^5,x,k\le n\)
Subtask1 (\(8\)pts): \(n,q\le 100\)
Subtask2 (\(12\)pts): \(n,q\le 5000\)
Subtask3 (\(12\)pts): \(x=0\)
Subtask4 (?pts): \(k=n\)
Subtask5 (?pts): \(n,q\le 10^5\)
Subtask6 (?pts): 無特殊限制

Day2 T2

給定序列\(a[0..n]\)與排列\(p[1..n]\), 將\(a\)序列按順序從上到下寫下來，相鄰兩數之間用長短不一的除法分數線連接(分數線短的先計算)，第\(i\)條分數線長度是\(p_i\). 有\(q\)次詢問，每次給出\(l,r\), 求\(a[l-1..r]\)與\(p[l..r]\)構成的分數的值對\(998244353\)取模的結果。
數據范圍: \(n,q\le 5\times 10^5,1\le a_i\lt 998244353\)
Subtask1 (\(12\)pts): \(n,q\le 100\)
Subtask2 (\(20\)pts): \(n,q\le 5000\)
Subtask3 (\(33\)pts): 保證數據隨機
Subtask4 (\(15\)pts): \(n,q\le 2\times 10^5\)
Subtask5 (\(20\)pts): 無特殊限制

Day2 T3

給定一張\(n\)個點\(m\)條邊的有邊權無向圖，邊權為\(w_i\le 10^4\), 點從\(1\)至\(n\)標號。除給定邊之外，對于每個\(i\)還在\(i\)與\(i\mod n +1\)之間連了邊權為\(10^9\)的邊。求該圖所有無序且兩點不同的點對間最小割之和對\(998244353\)取模的結果。
數據范圍: \(n\le 7\times 10^3, m\le 10^5,1\le w_i\le 10^4\), 圖可能有重邊，保證無自環。
注: 出題人原定數據范圍為\(n,m\le 3\times 10^4\).
Subtask1 (\(19\)pts): \(n\le 80,m\le 200\)
Subtask2 (\(23\)pts): \(n\le 300,m\le 1000\)
Subtask3 (\(26\)pts): \(n\le 1000\)
Subtask4 (\(32\)pts): 無特殊限制

總結

以上是生活随笔為你收集整理的PKUWC2020游记与题面整理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。