如何評價NOIP2017普及組複賽？

題目

---

跟樓上的差不多

T1 這不是裸的模擬么……

T2 怕ccf老爺機過不了 寫了個O(sigma(digits)*log(n))的map預處理，也沒什麼問題（這題用trie可以線性？）

T3 沒有弄什麼記憶化，看完題，往最短路的方向取想。這不是dijkstra么？格子為點，相鄰就建一條邊，曼哈頓距離為2也建一條邊（使用魔法，權值額外+2），正確性可以腦補一下，luogu民間數據能過。

T4 單調隊列優化什麼時候進入PJ的考綱了？不過這題比較裸，二分g，然後用deque優化一下dp可以把check()加速到線性（dp[k]是由一段dp[l...r]的最大值轉移過來的，區間[l, r)可以滾動）。然而。。。用stl的deque在luogu上雖然過了但是最慢的一個點跑了1500ms，感覺要被卡常啊。。。（為什麼我T2能想到ccf評測機的威力，這題就沒有花個5行手寫deque呢）

【T4 segment tree好像會掛】

總之，區分度……還行，估計會有一大堆200+。。。

但是。。。t4的考點真的不超綱么？【noip沒有考綱？

希望明年去考TG。

UPD: 啊？我都不敢相信

T3掛了啊。。。。。。

演算法是對的，但是居然沒有考慮【終點為無色節點但是可以由魔法染色】的情況。。。

dist[vertex(n,n)]作為答案不對，應該是min(dist[vertex(n,n)],min(dist[vertex(n-1,n)],dist[vertex(n,n-1)])+2)......

---

作為一位目擊一切的witness,我相信我有充分發言權。

難，但可以接受。第三題記憶化dfs（我本來不知道記憶化怎麼寫，竟然在賽場上開悟了，RP++）。然而，第四題腦子卡機，只寫了騙分。

oi的過來者都知道賽後AK的氣憤。賽後，輕鬆在半小時內AC第四題。在考場上也曾想到用DP，但是，沒有想到可以用二分優化。

這是我第一次參加noip，不錯，我是初三的。

本蒟蒻初賽沒過（謝謝老師的附加名額），複賽320左右，已經是我們學校最高了？

最後，一句忠告，考場上千萬別喝水！

---

t3寫了個複雜的dp然而樣例1都過不了。(???)

---

普及t1傻逼題，隨便做做，如果直接乘要卡精度

普及t2一般演算法直接暴力，奇葩演算法字典樹匹配後綴

普及t3一般演算法dfs，dijkstra，spfa之類的

普及t4二分答案+單調隊列+dp，據說要斜率優化？（大佬做法二分+線段樹+dp）

感覺比以往的普及難，t3據說都可以排到普及+（洛谷），t4更加不用說，雖然相對比較裸，但是題目表述比較坑

所以這是一套淦出題人的好題

---

剛考完普及的我

t1傻逼題 史上最水 被卡精度了 最後用了double 然後printf("%.0f")(?˙▽˙?)

t2字元串匹配 考場上忘了string里的find函數咋用 然後自己寫了一個 絕對AC y( ˙?. )耶~

t3寫dfs 一個小時122行 完美reヽ(#`Д′)ノ 然後騙分輸出-1 我覺得吧 t3dfs剪枝可以過 dp的話有後效性不能寫 只能是圖論了orz

t4....不會！騙分！好像正解是二分+加單調隊列+dp(加斜率優化？)....orz

總之 noip2017還是不錯的 畢竟第一次去 sd的日照一中真的不咋地 沒有電 都是上午普及去餐廳苟電 下午提高去餐廳苟電 嘛雖然沒電但也是很開心的 明年再去！

sd分數線205 剛好卡到205 嘛卡一等線賊開心嘿嘿嘿 洛谷也紅了 挺滿足

---

很噁心

已炸

退役

---

剛考完的蒟蒻：

t1無腦……題目中指出了不會出現小數；

t2難在數據範圍（500000）？直接用整型對後幾位取模枚舉大概不會超時；

t3……dp直接放棄，dfs加最優剪枝大概騙到不少分；

t4直接看當能獲得要求分數時（忽略減分格）跳躍距離和機器靈活度之差的絕對值最大是多少，

即為答案（也許是這樣）。

感覺比去年的題要好讀，去年題目描述很長讓人抓不到重點（或許是去年的我太弱了）

第一年參加普及，也是最後一年，對普及的難度略有些訝異-_-;

---

T1浪

T2浪

T3浪

T4？？？！

=========正文=============

T1：聽說有人真把小數乘上去了？

T2：坐看大佬秀水平。垃圾27隻能2循環+判後綴

T3：dijk有幸AC

T4：沒準備得分...40...

========後記==============

撞運氣的...考的全是我比較擅長的...

---

推薦閱讀：