注: 本文寫于11月17日傍晚。成績公布前暫時(shí)加密。

賽前

瘋狂頹廢。
前一天上午打了一下excrt的板子，看了一下\(O(1)\)快速乘等一些小技巧。
感覺自己一年比一年頹廢……吃棗藥丸
今年高一，不管怎樣心態(tài)都和初中時(shí)不一樣了吧。初中時(shí)打掛了還能慶幸自己年輕，現(xiàn)在打掛可真的就不是鬧著玩了……
看考場，發(fā)現(xiàn)和lrh&ll一個(gè)考場。我怎么覺得17年的時(shí)候我們就一個(gè)考場呢（雖然好像不在一個(gè)組）
考前繼續(xù)立flag,希望不要哭著出考場吧(noip2018&pkuwc2019兩次嘗試失敗)

11.16 (Day 1)

我的Day1體驗(yàn)和大多數(shù)低水平選手基本一致。
順序看題。
8:45左右寫完T1. 一遍過了樣例，但是\(n=64\)莫名會(huì)掛。最后把(1llu<<n)-1強(qiáng)行改成llong qwq[N+3]; qwq[1] = 1llu; for(int i=1; i<=N; i++) qwq[i] = (qwq[i-1]<<1)|1;才過。
9:10左右寫完T2. 本來覺得做法很虛容易寫掛，反復(fù)檢查了一下，結(jié)果一遍過樣例了。又去寫暴力，9:25左右拍上了。
1h切了前兩題，這勢頭不對(duì)，難道又是全場ak的day1……我打開了T3
這什么玩意？？他說的交換數(shù)字結(jié)果下面配圖很明顯是在交換編號(hào)啊？？？頓時(shí)蒙蔽，舉手提問題目是否有問題，得到了No response的熱情答復(fù)。
看了半小時(shí)，發(fā)現(xiàn)那個(gè)圖居然和我的習(xí)慣不一樣……那個(gè)圈里的數(shù)是數(shù)字圈外的數(shù)是編號(hào)……
這時(shí)候還有2h, 可是仔細(xì)看看這題我怎么一點(diǎn)思路都沒有啊……感覺情況非常的復(fù)雜，不是很好處理……
打了個(gè)10分暴力，又各花了0.5h想兩種特殊形態(tài)的部分分，依然毫無頭緒
什么……別告訴我我2.5h剛一道聯(lián)賽題只拿10分……我不接受……我不同意……
時(shí)間繼續(xù)流逝，我又先后嘗試思考正解、鏈、菊花結(jié)果屢屢失敗。
我感覺想吐……
然而靈光并沒有閃現(xiàn)。
day1結(jié)束，期望得分\(100+100+10=210\)

出考場之后強(qiáng)忍住沒有掉淚，不過心態(tài)也基本崩了……17年和18年我的day1分別是\(230\)和\(270\), 今年最多\(210\)了……真的有一種支撐不住的感覺
過了一小時(shí)和別人交流了一下，發(fā)現(xiàn)qdez基本都\(210\)……只有l(wèi)ky似乎想出了T3的\(O(n^3)\), 結(jié)果他寫炸了似乎要爆零，慘慘。
又去群里看了下發(fā)現(xiàn)大家都在抱怨T1T2sbT3難……突然感覺心態(tài)好了一些呢。
看到知乎上題解發(fā)出來了，T3的50其實(shí)挺套路的啊……為什么我就沒想到呢
傍晚gd初三巨佬zjr來問我估分，他\(235\), 還說GD全場都超過\(210\)了……我又開始崩了
最后聽說yamf T3都沒得超過10分，rqy&myh AK了，wqy T3沒做出，聽myh說集訓(xùn)隊(duì)有一半人不會(huì)T3……那這么說的話這場就沒有什么區(qū)分度了，我就當(dāng)今天什么都沒發(fā)生，day2加油。

11.17 (Day 2)

傳說中的有區(qū)分度的day2終于來了。
逆序看題。
T3, 怎么又是數(shù)據(jù)結(jié)構(gòu)，棄棄棄
T2, 看上去像斜率優(yōu)化？毒瘤，棄棄棄
T1, 計(jì)數(shù)？？怎么現(xiàn)在計(jì)數(shù)都被放到T1了？沒辦法，剛剛剛
8:40 我終于看懂題了嚶嚶嚶
8:42 第一思路是枚舉做了多少菜，發(fā)現(xiàn)不可做
8:46 轉(zhuǎn)換一下思路發(fā)現(xiàn)最多一道菜會(huì)違反一半的限制，可以枚舉，然后就相當(dāng)于這一個(gè)比別的都多，dp一下，\(O(mn^3)\),一臉懵逼
8:48 發(fā)現(xiàn)我的轉(zhuǎn)移枚舉選哪個(gè)是廢的，\(O(mn^2)\), 應(yīng)該沒假吧
寫了滾動(dòng)數(shù)組dp, 因?yàn)榍蹇諉栴}掛了15min,調(diào)過大樣例的時(shí)候大概是9:10
計(jì)數(shù)題……不拍了不拍了不虛，看T2
看到樣例3, 一個(gè)\(28\)位數(shù)赫然地?cái)[在題面里，出題人你真的不嫌自己毒瘤嗎
冷靜了一下，似乎和斜率優(yōu)化沒什么關(guān)系？有一個(gè)顯然的\(O(n^3)\) DP是設(shè)\(f[i][j]\)表示當(dāng)前劃的最后一段末尾是\(i\), 前一段末尾是\(j\), 發(fā)現(xiàn)轉(zhuǎn)移可以優(yōu)化，\(O(n^2)\).
寫完了，我怎么又一遍過樣例了？？感覺這次畫風(fēng)好奇怪啊，代碼難度大幅降低？還是我太菜了想不出代碼難度高的正解？
又想了一會(huì)沒想到什么比較好的優(yōu)化，感覺是個(gè)貪心又沒有貪心策略，于是開了T3.
\(40\)分顯然白送，鏈顯然白送，然后呢……完全二叉顯然白送……嗎？？我感覺我好像不太會(huì)寫啊.jpg
于是先去寫了一個(gè)\(O(n^2)\), 又一遍過樣例了，今天這是怎么了……鏈的\(15\)分過會(huì)再寫吧
想了一會(huì)正解，感覺沒什么思路，只想到了一個(gè)求子樹內(nèi)重心的做法: 重心顯然滿足到所有節(jié)點(diǎn)距離和最小。那求距離和是一個(gè)dp, 我把dp數(shù)組表示成\(at+b\)的形式, \(t\)是樹總大小，然后線段樹維護(hù)凸包，就可以輕松應(yīng)對(duì)子樹內(nèi)了……子樹外……沒啥想法啊……
又看看數(shù)據(jù)范圍，\(n\le 3\times 10^5,T\le 5\), \(O(n\log n)\)都很難通過，線段樹維護(hù)凸包可以去死了……
我是不是要止步\(100+64+55=219\)了？這樣的話我離考過去年還差\(3\)分，不甘心……還有1h40min, 我能怎么辦……
現(xiàn)在我還有兩個(gè)選擇，一是想T2正解，二是莽T3的完全二叉樹(因?yàn)槲易灾獢?shù)據(jù)結(jié)構(gòu)水平太低想不到正解)。我決定先想一會(huì)T2，然后再去想T3.
打出DP表，發(fā)現(xiàn)固定\(i\)在合法的前提下\(f[i][j]\)隨\(j\)的增加而不升，然后又證了一下感覺挺顯然的，那么其實(shí)就是要讓每次劃分最短。哦這么顯然的結(jié)論我都要打表觀察……我是個(gè)弱智么？！
此時(shí)我過于激動(dòng)，想都沒想寫了個(gè)\(O(n)\)雙指針找決策點(diǎn)，一發(fā)過了前兩個(gè)樣例，好，我穩(wěn)了！測第四個(gè)樣例(第三個(gè)是高精測不了)，比答案大了好多……
難道結(jié)論錯(cuò)了？拿暴力程序跑了下，\(dp\)數(shù)組是單調(diào)的啊？？那是怎么了？？哦，決策點(diǎn)顯然不能直接雙指針求……我果然是個(gè)弱智
那怎么求啊？似乎只能二分+線段樹\(O(n\log n)\)? 線段樹……我真的能寫出來嗎……
T3還有\(15\)分暴力沒打，T2還生死未卜，看著右下角的時(shí)間11:01, 渾身無法阻止地冒著冷汗……
冷靜一下，每次覆蓋，單調(diào)棧就行了！可是還有兩個(gè)該死的二分去不掉，\(O(n\log n)\), 整理一下思路，開始寫吧……
比我想象中的好寫一些，十幾分鐘寫完了，調(diào)了一會(huì)發(fā)現(xiàn)二分的方向反了，改過來過了所有樣例！
還有30min, T2來不及對(duì)拍，快馬加鞭寫了個(gè)T3的\(15\)分暴力, 這恐怕是我兩天寫得最不順的一個(gè)代碼，掛了好多次……
11:47, 我終于調(diào)過了樣例，期望得分\(100+88+55=243\).
最后十幾分鐘覺得對(duì)拍意義不如肉眼檢查，于是檢查了十幾分鐘文件名、輸入輸出、數(shù)組和空間，T2精打細(xì)算開了\(1000 \text{MB}\).
結(jié)束的那一刻，我把T2的數(shù)組從\(4\times 10^7\)改成了\(10^6\). 我不配寫正解，我不配開大數(shù)組……
總期望得分\(100+100+10+100+88+55=453\), 感覺墊底水平……但愿別掛……

考完后直接返回(沒有掉淚，flag成功達(dá)成)。途中交流了一下，hyw和nyd怎么都說自己T1不會(huì)寫了\(84\)喵喵喵？
hyw貌似考得不是很好，估分\(84+64+55=203\)左右，lky好像也不太好，jxp估分\(100+64+75=239\), 不知道gmt和yzx怎么樣。(這也許是qdez今年最有競爭力的五個(gè)人？)
比我低兩級(jí)的巨佬sqy估分\(245\), Orzzzzzz... 我被本省初中生吊打，沒救了……
在gzez一起訓(xùn)練的scx,lh貌似直接心態(tài)崩潰……scx昨天\(210\)大眾分，今天自稱t1沒調(diào)出來，寫了個(gè)指數(shù)級(jí)暴力；lh自稱d1t2寫掛……默哀
zjr自稱估分\(219\), 但是我不會(huì)忘記他外號(hào)“張假瑞”的由來（大霧）
看上去大家得分都不是很高，如果我不掛的話還是有希望的……但愿別掛分……

總結(jié)與反思

這次也許我最想質(zhì)問自己的一個(gè)問題是，為什么我經(jīng)過這么長時(shí)間的訓(xùn)練，還想不出Day1T3的50分那種比較套路的東西？
也許我會(huì)找出借口: 全SD也沒幾個(gè)人想出T3的50分啊。可是，所謂競賽就是要選拔出最尖端的那一撮人對(duì)吧。現(xiàn)在搞OI的人越來越多，如同千軍萬馬過獨(dú)木橋，如果我永遠(yuǎn)抱著別人都不會(huì)我也不會(huì)的心態(tài)，每次都拿大眾分，還有什么勝出的可能？
現(xiàn)在的OI大概已經(jīng)告別了那個(gè)比拼熟練度和穩(wěn)定度的時(shí)代，因?yàn)槭炀毢头€(wěn)定已經(jīng)是對(duì)一個(gè)OIer的基本要求，而非用來區(qū)分選手的標(biāo)準(zhǔn)。在這種情況下，假設(shè)我連基本的套路都掌握不明白，又沒有過人的天賦來做出神仙題，大概只能成為大佬的炮灰吧。
初二，初三，高一，盡管我自己在不斷進(jìn)步，卻趕不上時(shí)代進(jìn)步的速度。去年ZR十連測，我的成績最后基本穩(wěn)定在20名左右。今年ZR十連測，我的成績依然在20名左右(而且失誤掉下去的次數(shù)還在增加)，永遠(yuǎn)成不了最尖端的那一部分，省隊(duì)將與我有何緣？
因此希望自己以后做題的過程中一定要多積累一下值得借鑒的思路，并對(duì)這些套路有足夠的敏感度。(當(dāng)然也不能過敏，忽視了反套路思維的訓(xùn)練)
除此之外，自己的努力程度也明顯不夠。高一的四分之一已經(jīng)過去，如果再不拼盡全力，明年成了一條命選手，驀然回首發(fā)現(xiàn)自己枉度五年光陰，將是何種情境，自己心里清楚就好。

賽后

upd 11.18: 發(fā)現(xiàn)day2t2我居然把一個(gè)單調(diào)的東西放在單調(diào)隊(duì)列里二分……我是智障

upd 11.18: 在學(xué)校上著上著課，突然腦中如雷擊般閃過一個(gè)問題。
我的day1t2。
嗯，我代碼原來是這樣的

const int N = 5e5; int cnt[N+3];

本機(jī)對(duì)拍\(10^5\)組\(n=500\)的數(shù)據(jù)沒出現(xiàn)問題，但考試結(jié)束前發(fā)現(xiàn)cnt數(shù)組需要用到負(fù)下標(biāo)，于是改成了:

const int N = 1e6; int cnt0[N+3]; int *cnt = cnt0+N;

更致命的是，我改完之后連測都沒有測直接交了上去。
附正確寫法:

(1)

const int N = 5e5; int cnt0[(N<<1)+3]; int *cnt = cnt0+N;

(2)

const int N = 1e6; int cnt[N+3]; //因?yàn)閚<=5e5, 因此負(fù)下標(biāo)會(huì)爆到前一個(gè)數(shù)組的后半部分，不產(chǎn)生任何影響

多少條正確的道路，我卻偏偏走上了錯(cuò)誤的一條。
吊 死 于 括 號(hào) 樹 上
預(yù)估分\(100+0+10+100+88+55=353\), 那真的啥都別想了。
高一容不下失誤，一招不慎滿盤皆輸。

upd 11.20: 代碼終于發(fā)了。
我day1t2并沒有開錯(cuò)數(shù)組，是我的印象出現(xiàn)了偏差。
但是day2t2因?yàn)橐恍┲钦显驋斐闪?span id="ze8trgl8bvbq" class="math inline">\(64\)分。
洛谷得分\(100+100+10+100+64+55=429\). 有一定希望進(jìn)營吧。
附day2t2掛題方式:
代碼:

int n,typ; llong a[N+3]; namespace BruteForce //200 MB {void solve(){for(int i=1; i<=n; i++) scanf("%lld",&a[i]),s[i] = s[i-1]+a[i];......} } namespace GG {void gen(){//讀入typ=1的數(shù)據(jù)}void solve(){if(typ==1) {gen();}......} } int main() {//freopenif(typ==0) {for(int i=1; i<=n; i++) scanf("%lld",&a[i]);}scanf("%d%d",&n,&typ);if(n<=5000) {BruteForce::solve();}else {GG::solve();}return 0; }

初始\(typ=0,n=0\), 所以并沒有讀入a數(shù)組，但BruteForce中有讀入a[i],GG中沒有.
我的本意是把a(bǔ)[i]的讀入放到main()函數(shù)里。因此我運(yùn)氣好撿了\(64\)分。一切都是迷惑行為……
這大概就是走的時(shí)候檢查太倉促，沒有好好檢查讀入和數(shù)據(jù)分治的后果吧。
也許我本來只能通過這題\(88\)證明自己不是個(gè)什么都不會(huì)的暴力選手，結(jié)果它掛成了標(biāo)準(zhǔn)的暴力分。

總結(jié)

以上是生活随笔為你收集整理的CSP-S2019游记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。