如何評價NOIP2016提高組複賽試題？
作為初賽爆零複賽沒參加的老年半退役選手，先佔坑。。。
說實話啦，因為我不在國內，沒法參加OI生涯最後一場NOIP，於是對題目發表些個人點評減少一點遺憾吧……
——考完啦——
老年選手不知道具體題面只是聽了問題概述QwQ1.模擬不說了，考你會不會編程2.首先對每條路徑從LCA處分成兩半，那麼兩半的路徑都是自上而下走或者自下而上走，令di表示第i個幾點的深度，那麼自上而下走的人能夠影響的詢問始終滿足wi-di=Constant，自下而上走的人影響的都是wi+di=Constant的詢問。接下來利用算出的Constant把詢問分類，把樹上自上而下的鏈拆成下端+1，上端-1，那麼對每一類詢問做子樹和就能得到每個點的答案了，不能做n遍dfs求子樹和，但只要預處理最近同類詢問祖先就可以一次dfs解決了。
3.注意到兩輪之間的路徑只跟兩輪有沒有申請有關，預處理出四種情況的期望路徑長度（兩邊都不申請，前一輪申請，後一輪申請，都申請），然後直接做背包dp就可以了，f[i][j][k]表示前i輪已經申請了j個其中第i個申請狀態為k（k為1表示申請0表示不申請），枚舉下一輪申不申請就行了。——以上胡亂碼了個題解，看不懂就對了反正我沒寫代碼全是意識流（霧）——
首先難度較近年有大幅提高，感興趣的可以看一下去年的第二題：http://uoj.ac/problem/146 感覺去年第二題……怎麼說呢，這也能出出來我是比較服的。而今年的第二題說實話已經達到了NOIP第三題的難度，甚至很多集訓隊員都沒有想出做法，而是使用高級數據結構（如啟發式合併主席樹）強行維護詢問來解決，還有被卡常數的風險。
但是上面說的這個演算法只需要簡單的求出LCA然後進行樹上深度優先遍歷就能解決，簡單的知識點的背後是的較高思維難度。我很贊成這樣的題目，然而放在第一天第二題可能確實難了一些，不知道選手們做的怎麼樣。至於第三題，我覺得挺莫名其妙的，第三題只要理解了期望的含義，很容易就能看出非常樸素的背包模型，不需要什麼思考就能做出來，屬於動態規劃的「套路題」。鑒於這是NOIP第一次設計數學期望，對選手來說本題的難點很可能在於理解數學期望，而非對求解方式的思考。當然這也可能是命制高質量的動態規劃題比較難，而動態規劃又是很重要的思想必須要考的緣故。
總的而言，難度提升，代碼量提升，思維考察提升，第二題和第三題換一下可能合理些（霧）？
——Day2考完辣——
先來個意識流題解。。
1.在模k意義下直接求出所有組合數，然後二維前綴和統計0的個數即可。
2.注意到相鄰兩次切下來的長度，增加量不會超過q，而之前切的蚯蚓沒秒鐘增加q的長度，所以後切的蚯蚓一定比先切的蚯蚓短，於是開三個隊列，分別維護初始的蚯蚓，切得的前一半蚯蚓，切得的後一半蚯蚓，新蚯蚓直接加到隊尾就可以了，時間複雜度就線性了。3.狀態壓縮DP，f[s]表示集合s的豬已經被消滅了，還需多少次發射，注意到兩頭豬和遠點就能確定一個拋物線，直接枚舉兩頭豬是轉移是n^2的，注意到所有豬最後都要被消滅，於是標號最小的未消滅的豬是一定要被消滅的，不妨就在此回合消滅它，那麼枚舉另一頭豬的複雜度是n的，預處理兩頭豬確定的拋物線能消滅的豬的集合，可以做到O(n)轉移，於是複雜度就是O(2^n*n)了。——奇妙做法——
2A.聽說左偏樹常數小，不妨來寫一個說不定能卡過去。2B.二叉堆太low了，我們使用32叉堆，在堆上維護時使用位運算，似乎會被卡空間。3A.對於每個子集，判斷能夠用一隻鳥一次性消滅，能的係數為1，否則為0，得到一個集合冪級數。我們可以二分次數k，那麼我們求這個集合冪級數的k次方集合併卷積，並判斷全集前的係數是否&>0，大於0說明可以消滅。這樣複雜度是O(2^n*n*logn)，快速沃爾什變換(FWT)常數很小，感覺跑過去還是比較輕易的。3B.敦敦敦說：其實fwt用取模，也可以一個n。哦我也不大清楚這是怎麼搞的。。——我也不知道在這個分割線上說什麼——
這次NOIP，可以說專治各種高級數據結構學傻，高級演算法學傻（霧），比如第一天第二題第二天第二題很容易走進高級數據結構的不歸路，我這個FWT學傻了的老年選手看了D2T3直接想出了演算法3A。。。演算法3是yjq教我的。。
我認為NOIP從命題質量上提升了許多（可對比去年D1T3），即更加註重對思維的考察，代碼能力考察也是在有了相應的思維能力之後才會有。注重思維考察一個相應的結果就是難度大幅提升，會提高在NOIP選手中，中等等水平往上的選手之間的區分度。
總體來說給題目點贊~
P.S.對於部分分設置，我根本沒看，所以不知道對於剛接觸OI的新手是否友好。swap（T2，T3）upd:swap（Day1，Day2）
話不多說 上圖三張
看評論貌似侵了？
請私信我，有侵必刪，謝謝mengbier and mogician這noip藥丸
考點全部被我在近兩周壓中，然而學生依然做的夠挫的、這兩周一共就給學生複習了組合數學，包括期望，優先隊列，lca，dfs維護路徑上的信息，dp唯獨強調了狀壓，基本全中了啊，然而估分一個個的讓我眼前一黑。
每天看到題的一瞬間，我是這樣的
考完詢問情況、我是這樣的：
估完分、我是這樣的：
好事隨著國內OI的發展，一些略高於noip難度的知識加入了noip套餐(這樣一些出題人就可以理直氣壯地出noiplus模擬賽了（劃掉鼓勵noip選手學習一個，提高姿勢水平（這個用意在第一題里很明顯嘛（霧希望OI繼續發展，妙題越來越多畢竟競賽攻堅比文化課求穩有趣多了嘛← ←（劃掉
這個時候應該強答一波
之前參加過NOIP 13到15這三年都很水， 頂多有一道防AK題， 但反正都是那種你看完題就大概知道怎麼做的題
考之前感覺這把極穩， 甚至還給學弟說：NOIP考期望我直播吃鍵盤考試的時候感覺挺正常的， d1t2沒寫線性而已。其他題都沒被套路。
昨天突然發現， d2t3轉移忘了break了（做法參見lzz的演算法3）
哇哦， 變成了2^n*n^2， 看來是要被卡了， 唯一一個AK的機會GG了
總的來說， 比前幾年思維難度確實上升了，但是考慮到OI每年都在進步，這也是很正常的。而且符合大流。 順便還能篩出實力強的選手。個人感覺畫風很不錯， 如果數據不水就更好了
不過問題來了， 哪裡有巧克力味的鍵盤？
UPD：有人問直播地址， 等我先找到巧克力做的鍵盤再說QAQ， 滿臉都是淚。 再亂立Flag我就是狗（滑稽）NOIPNOI PopularizedNOI Professional
這時候我們需要 @NanoApe，這位兩小時的ak爺來回答。
d1t2出得很好，而且解題的思路可以從數據分布說明裡得到啟發。我為命題人點個贊。
d1t3出得很不好，首先是題目背景要求的預備知識過高，其次是知道了這些知識之後，這題目思考難度就瞬間下來了。
預言明天最後一題是非常複雜的搜索題目，其餘兩題應該會比較簡單。不然很難解釋為何d1t2不能選作最後一題。2016 12.09更新
分數線出來了保住菊花 省一了總算不是省三選手了2016 12.02更新成績出來了為什麼掃了一眼500+的都是上一年的省隊選手啊 打菜雞局屠殺小朋友也不要這樣啊感覺我省省一會切到 300分看來今年又只能拿省三了2016 11.21更新
由於某些原因 答案被建議修改了（我不就膜了一下嗎以下正題今年day2難度總體和去年持平 比前年稍難一些首先是d2t1 顯而易見這是一道數論題然後就有人硬莽組合數公式了 然後就爆炸了其實仔細看題就能發現k特別小 於是就能想到一個簡單的方法 分解質因數然後瞎幾把枚舉就好了總體難度和前兩年持平 （我才不會說我去年d2t1翻車了之後是d2t2看完題目就知道是堆 總算出了一道正常難度的題目了然後看看數據範圍
怎麼有線性做法啊？？？
想了十分鐘不會於是考後問了其他選手zy：這不是傻逼題嗎 開三個數組...好了我真tm智障正解就是開三個數組 一個存原來蚯蚓的長度 一個存被切過的前半邊 一個存被切過的右半邊 由於這些蚯蚓保證單調 所以不需要堆維護總體難度和去年t2持平 或者稍微難一些然後是d2t3看題目 憤怒的小鳥去年有鬥地主 前年有flappy bird 明年是不是要考植物大戰殭屍了不對 植物大戰殭屍貌似noi出過還是德州撲克靠譜一些看一下題面「Kiana正在玩憤怒的小鳥」玩個毛啊 以至於想這題的時候滿腦子都是「我不要治療 我要喝芽衣的妹汁」
然後看完題目 拋物線 靶子 怎麼有點像hnoi的某題啊
然後想想不是半平面交那要怎麼做呢很明顯有個性質 按照高度排序 從高往低枚舉 然後再枚舉一個點 用一些瞎幾把貪心就能過了（當時我想n=1000）看完數據範圍我瞎了n=1818別說了 鬥地主加強版對狀態狀壓即可注意精度總結d2難度和去年持平 都是一道正常題+腦力題+代碼題總體難度可以接受 是一套不可多獲得的好題啊 黑澤黛雅實名反對各種noip考鬥地主 和鬥地主魔改題目 ---------分割線-----------今年d1題目是要搞事情啊以下正題今年noip d1題目總體難度比去年還有前年的題目不知道難到哪裡去了首先是d1t1 今年d1t1題目巨長無比。而且xxer和mogician也很容易想到fate和膜...然後你就發現這道題是一道模擬 和取模有關題外話（這種在題面中就把題解告訴你的題目實屬少見...一個膜告訴你了這是模擬和取模）總體難度較2015年和2014年稍難 細節也相對於前兩年多 是一道合格的t1------之後是d1t2 今年的t2一改前兩年的風格 估計出題人覺得連送兩年分不太好 於是一失手 出成了這樣估計所有人看到t2前的感覺
看完t2時候的感覺（分數改成25）
（情有可原 你見過noip考概率dp嗎）
所以這道題相比去年和今年前年的t3 代碼量明顯減少（無論是討論情況更多的小鳥 還是細節多到吐 婊的飛起的鬥地主）今年的t3就像t3中的一股清流 難度自然沒有前兩年高（當然你不會概率dp的話 確實理解起來有點難度）----總評今年noip難度總體上升 就我所知 我校參加noip的學生 有兩人寫出t2（其中一個是 @閆書弈）6-7人寫出t3 大部分人寫出t1 今年noip難度總體上升 並且首次加入概率dp作為考題 說明了noip以後考splay也不是稀奇的事情了代碼量比去年低 但比前年高 充分抑制了考完玩掃雷的行為思維題目難度大 t2拿去出noi都不為過D1T1我是mogicianD1T2我是mengbierI good vegetable a.
以前出noip模擬題的人開始出noip真題了
更新：
tie(D1T1, D1T2, D1T3, D2T1, D2T2, D2T3)
= make_tuple(D1T1, D2T2, D2T3, D2T1, D1T3, D1T2);
（逃
---------------- 分割線 ----------------
CCF的那個出題人，比你們不知道高到哪裡去了！話說感覺D1T2比D1T3難……然而只會寫騙分代碼（逃
作為一個今年退役的高三狗…個人覺得今年來說總體難度會高於去年，尤其D1…
D1第一題超級水…不到五分鐘就碼完，甚至比去年簡單，有點嚇到我第二題的話就有點開始蒙蔽，一開始想寫普通Tarjan的LCA但是發現可能要記錄路徑…又轉戰倍增，然而倍增忘了怎麼寫，開始蒙蔽想數據結構（跳入出題人的坑），奈何看看時間認為寫不完這數據結構，果斷暴力60分第三題從題面上來講會比較難理解，所以我一開始沒去想第三題，以為很難，於是在第二題花了太多時間，當我發現這是個很簡單的DP時已經來不及了…不知道能過多少分D2的話第一題有一點難度，對高一高二可能不是很友好，畢竟他們可能還沒學組合數遞推式，但是楊輝三角也挺容易理解，所以不是很難，但也不水第二題q=0的情況用一個優先隊列維護隨便都能拿65，有寫出來但是我不肯放棄一直想，讓我想到了一個可能滿分的做法…用線段樹維護這些蛇的長度及其編號，每次取最大值然後把他編號前後的加上q，在插入這兩條切完後的長度（新的長度編號為n+i），但是沒寫freopen這些都沒用…第三題依舊是沒來得及寫…果然我這種蒟蒻很容易犯錯誤估計還是省二了~作為一個退役oi選手，監考人員，來說說對於這屆noip感想吧，day1和day2應該對調吧，day1t2該放t3吧，不過還是一如既往的水水的，感覺今年分數線會蠻高的，還有數據點標的很詳細，很良心_(:з」∠)_還有選手們各種有意思啊
UER早已預示了一切（現在還有誰說UER不是NOIP難度的？）
我只服mengbier mogician
————————————————我只想說，Kiana你應該去玩太空版angrybirds。最終得分：100+25+32+100+60+75=392非常令人滿意的結果了。代碼發下來後確實發現自己當時很多傻逼的地方，像d1t3沒判重邊，d2t3強行2^n*n^3(預處理下就可以直接優化一維)，這些其實是可以避免的失誤。感謝出題人d2t3沒卡精度，不然這把gg。這回我的心算是正式放下了。由於我不打算省隊，所以是光榮退役了。感謝OI陪我多年的時光，現在要回歸準備高考了。演算法競賽，我們有緣再會。=====更新分界線=====山寨數據測過了，預計350-400分，SC應該沒什麼問題吧。。希望不是一口毒奶qwq=====更新分界線=====D2:我靠，簡直swap(d1,d2)啊！第一題一開始想錯了，寫了個k是質數才能過的方法，後來對拍發現了，簡直差點gg。對拍大法好。瀏覽完題面後，發現第三題跟openjudge上一道矩形覆蓋很像(敲出代碼後發現真的差不多)，所以先把第三題做了。最後做第二題，斟酌了一下選擇用stl的優先隊列水過去了。肯定會t若干個點，不過就考試的時間分配上來說還是比較划算。對拍第二題有個小插曲，對拍時發現答案不一樣，那時已經快考試結束了，把我給急得。最後發現是我暴力寫錯了233。第三題全程沒管m，用了n^3*2^n的演算法，極限數據目測t了。第三題沒有對拍(感覺暴力不好寫)，而且還有精度問題，所以並不知道第三題穩不穩qwq總的來說思維難度d2比d1小，而且感覺兩天t3都比t2簡單。這次考得挺玄乎的，希望分數好看點qwq=====更新分界線=====D1:心態爆炸D1T2開始捉急，T3想都沒想開始寫暴力，總之gg了
福建 OIer 表示棄療了還沒有掃雷可以玩，差評。
---------- update - Day 2 ----------
吸取了 Day 1 的教訓，Day 2 早早棄療寫了個 2048 玩。
---------- update ----------
對了，我還把 2048 附在 D2T1 的代碼注釋里了推薦閱讀：
※如何評價NOIP2015提高組複賽試題？
※如何評價NOIP2017提高組複賽試題？
※你作為 OIer 出的最好的題有哪些？
※如何看待信息學奧林匹克國家集訓隊當前第一名放棄參加冬令營及後續選拔？
※如何評價中青報「多數奧賽金牌得主難成大器」一說？