NOIP 2017 总结
NOIP2017 總結(jié)
DAY 0
又到了一年一度的NOIP……
傍晚6點多才從學(xué)校出發(fā)，到廣州已經(jīng)8點出頭了。
不過酒店比之前好了不知道多少，各種設(shè)施齊全。
和同學(xué)玩耍了一會兒，便進入了夢鄉(xiāng)。
DAY 1
6:25早早被鬧鐘叫醒，本來還想再睡一會，
一想到要NOIP便心情激憤，睡意全無。
于是就去吃早餐，早餐還不錯，有很多東西吃。
坐上大巴去考場，8:15都到考室了。
結(jié)果還不能試機，白白坐在位置上等。
（幸好剛坐下來的時候已經(jīng)試了一會兒，~偷笑~）
終于打開了題目，便聚精會神開始看題。
第一題一看沒什么思路，心里就有點慌，心想這不符合NOIP的風格啊？
第二題就是一道純模擬，比較簡單（心情平復(fù)了許多）。
再看第三題，有點像根據(jù)SPFA來DP之類的。
于是開始搞第一題，手出了幾個數(shù)據(jù)發(fā)現(xiàn)沒什么可搞，
但是似乎發(fā)現(xiàn)了一些規(guī)律，答案似乎是a*b-a-b！！！
于是我激動地打了個暴力，一拍——居然沒問題！！！
這下穩(wěn)了，我信心滿滿地開始打第二題。
沒想到這題其實細節(jié)挺多的，一遍打下來樣例錯的很離譜。
于是只能無奈地調(diào)試，調(diào)出了三四個錯誤，終于過了小樣例。
（吐槽C++不能直接換行，就算用\n換行了在LINUX下也要換成\r，很麻煩）
所以我只能一個一個讀入完才沒事。
測完小樣例又測大樣例，結(jié)果又出錯了！
十分無奈的我又找出了兩三個錯誤，這下總算沒錯了。
我十分不放心地又出了幾個小數(shù)據(jù)，發(fā)現(xiàn)沒問題。
這時才10:30不到，還是比較穩(wěn)的。
接著又興致勃勃地開始打第三題。
打了一會兒自己之前想的那個DP，又花了點時間調(diào)試，
這才終于過了樣例！
可我還是高興得太早了，一測大樣例發(fā)現(xiàn)輸出的答案比正確答案大了很多。
開始時我還傻傻地以為是DP重復(fù)轉(zhuǎn)移了，就又花時間修改了轉(zhuǎn)移的方式。
結(jié)果還是大很多，我有些百思不得其解。
之后想了想才發(fā)現(xiàn)原來直接DP有后效性！！！
時間只剩下15分鐘，完了，爆炸了！！！
我驚慌失措地開始打30分 k=0 的暴力，過了樣例就沒管它了。
再檢查了一下程序比賽就結(jié)束了。
在車上大家交流題目，發(fā)現(xiàn)大眾分都是200+，第三題果然很坑~~~
下午乖乖待在酒店。。。
晚上還是去二中吃飯，飯菜還不錯，有水果吃，還有雞吃（美味）。
晚上乖乖待在酒店。。。
DAY 1 評測結(jié)果：
自我估分：100+100+30=230
學(xué)軍數(shù)據(jù)：100+100+0=200
洛谷數(shù)據(jù)：100+100+0=200
第三題怎么回事呢？？？
原來如果是有環(huán)的情況還是會出現(xiàn)低級的重復(fù)轉(zhuǎn)移！
這樣答案還是會算大！應(yīng)該倒過來做一遍先才行！
DAY 2
6:45被鬧鐘和DDX叫醒，比昨天睡多了20分鐘懶覺。
一想到今天DAY2，頓時心情激憤，睡意全無！*2
又有得吃美味的酒店早餐，還喝了瓶酸奶和奶茶。
又坐大巴去二中，路上還小小的補了補覺。
進了考室，吸取昨天經(jīng)驗，先“偷偷”試一下機。
題發(fā)下來就開始努力想題了。
第一題就是并查集簡單題，之前都有做個類似的原題，都不怎么要想。
第二題開始時沒什么思路，看到 n≤12 覺得可能是狀壓或者直接搜索。
第三題也沒有太多思路，只能拿部分分。
直接開始敲第一題，幾乎一遍過，樣例都沒怎么研究。
過了小樣例和大樣例之后不怎么想拍，肉眼檢查了一下就不管了。
心里覺得第三題更能拿分，就開始想第三題。
但是一直不能解決空間問題（表示不會神奇的動態(tài)開點）。
無奈之下決定先打了個30分的暴力。
很快我便過了樣例，覺得沒什么好搞就去打第二題暴力了。
可是由于我搜索能力太差，居然不會枚舉父親來轉(zhuǎn)移（都不知道我當時怎么想的）！
覺得暴力沒什么希望的我決定打一個40分BFS直接構(gòu)造。
很快也過了樣例，這是大概是10:15左右。
我還是有點心慌，這樣的分數(shù)就只能賽季報銷了！
于是我專心開始研究第三題。
觀察很有規(guī)律的數(shù)據(jù)范圍，我突然眼前一亮！
咦？！n=1 ！也就是說只有一行！
還說什么，直接Splay啊！（NOIP里的平衡樹……）
猶豫了幾秒鐘之后，我下定決心開始狂敲。
打了半個鐘左右過了樣例，但心里很虛。
就打了個拍，用之前的暴力拍我的 Splay，沒有問題，20分到手。
我美美地繼續(xù)思考，又發(fā)現(xiàn) q≤500 似乎也可以做。
摁了摁計算器，發(fā)現(xiàn)只需要開個 Vector 就能解決空間問題了。
因為最多只修改 500 次，沒修改過的那些的編號還是原編號，就不需要開空間存了。
我又一頓狂敲（中途因為對 Vector 有少許不熟卡了卡）。
終于艱難過了樣例，我長長地舒了口氣。
心里很虛的我又用暴力拍我的 Vector ，發(fā)現(xiàn)沒什么問題，又有20分到手了。
這時我的第三題已經(jīng)拿到了70分，但我決定還是繼續(xù)發(fā)掘部分分。
我又發(fā)現(xiàn)當所有事件的 x=1 時，所有修改都發(fā)生在第一行和第 m 列。
太好了，用兩棵 Splay 維護那兩行不就行了嘛！
我很爽地將之前那一大段 Splay 復(fù)制了一遍，把數(shù)組名改一改就好了（真爽）。
結(jié)果因為有些數(shù)組名沒改過來又調(diào)了很久（不爽）。
就這樣我終于打完了 4000 bytes 的程序，而且沒有拍出錯（成就感++）
那么我的第三題拿到了80分，比之前的簡簡單單的30分多出了整整50分！
頓感努力拿部分分真好！
時間還剩半小時，我決定在第二題上水點分。
發(fā)現(xiàn)它的值會很接近在最小生成樹上構(gòu)造，
于是我打了一個最小生成樹 加 枚舉根用BFS按深度搜索。
這樣估計能水點分吧。
檢查了一下程序之后，比賽就結(jié)束了。
大巴上與同學(xué)們討論了一下試題，我恍然大悟，
發(fā)現(xiàn)第二題的暴力很好打，只需要 n^n 枚舉每個點的父親，
這樣就能構(gòu)成一棵樹了（感嘆自己的暴力水平–）。
而且再加上一個估價函數(shù)就能秒過本題！
就這樣，我的NOIP2017結(jié)束了，我們一行人坐車回了學(xué)校。
DAY 2 評測結(jié)果：
自我估分；100+40+80=220
學(xué)軍數(shù)據(jù)：100+45+50=195
洛谷數(shù)據(jù)：100+60+50=210
什么？第三題居然爆炸了？
啊啊啊！！！沒有開long long！！！
我居然沒想到 (3*10^5)^2 會爆 int ！！！
這下棄坑了，辛辛苦苦打的兩棵 Splay 白打了……
這真是太粗心了，“馬失前蹄”啊，還是不夠細致。
不過還好，第二題果然水了點分（好險）。
——總結(jié)——
這次的NOIP做的不是很理想，比如說細節(jié)沒有把握好。
連 long long 都不記得開了，暴力又不會打，
對時間和部分分也沒有很好地把椌。
不過還好的是該切的題都切了，DAY1第一、二題，DAY2第一題都過了。
正常總分( DAY1 + DAY2 )：
100+100+0 + 100+40+50 = 390
希望下次能考出一個更好的成績吧！
與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖總結(jié)
以上是生活随笔為你收集整理的NOIP 2017 总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： JZOJ 5462. 【NOIP2017
- 下一篇： JZOJ 5476. 【NOIP2017