如何評價NOIP2017提高組複賽試題？

12-29

三道題都有一股濃重的Codeforces的氣息，分別像是div2的A,C,E三題，不知cf上能不能找到原題（滑稽

t3正解是O((n+m)(logn + K))，常數非常捉急，希望出題人設時限的時候要對ccf老爺機的常數有一定的了解。既然出的是cf風格的題目，就要有cf速度的評測機。

那個大樣例，我要跑0.34s，經過重重優化優化到了0.30s，三組數據就是0.9s，ccf的老爺機的時間再乘個4至5倍，應該還是會超時。

附贈題解：

T1：math

直接輸出A*B-A-B。

T2：complexity

用棧模擬，模擬時記下所有未被銷毀的名字集合，以及當前層的複雜度的維數。

F i x y中，

若x=c1,y=c2,c1&<=c2，維數為0

若x=c1,y=c2,c1&>c2，維數為-inf(循環不執行)

若x=c1,y=n，維數為1

若x=n,y=c2，維數為-inf(循環不執行)

若x=y=n，維數為0

記得都判了。

T3：park

用dijkstra對所有1&<=i&<=N預處理出dis(1,i), dis(i,N)

一條從u到v的長為len的有向邊可能出現在答案的路徑中，當且僅當dis(1,u)+len+dis(v,N)&<=dis(1,N)+K。把沒用的邊刪去後，每條邊都有可能出現在答案中。

將每條從u到v的長為len的有向邊的長度替換成len-dis(1,v)+dis(1,u)後，問題變成了：「求從1到N的，長度&<=K的路徑的條數。」

因為把沒用的邊刪去後，每條邊都有可能出現在答案中，所以，如果此時仍然有僅由長度為0的邊構成的環，答案一定是無窮大。

現在考慮沒有僅由長度為0的邊構成的環的情況。dp[i][j]表示從1到j的長度為i的路徑的數量。dp的順序是：先枚舉i再枚舉j，i的順序從小到大，j的順序可以是任意一個由長度為0的邊構成的DAG的拓撲序。

時間複雜度O((N+M)*(K+logN))。

-------------------------------

考完了day2，day2的畫風比昨天舒服多了呢qwq。

依照慣例，附上今天的題解。

T1：cheese

簽到題，算算距離，並查集連起來。

如果存在一個聯通塊，使得這個聯通塊里既存在碰到下面的點，又存在碰到上面的點，答案就是Yes，否則就是No。

T2：treasure

嚶嚶嚶我考場上寫了一個O(n * 4^n)，害苦老命卡到0.7s，應該還是過不去的吧QAQ

先說我考場上寫的O(n * 4^n)做法吧

dp(i,s1,s2)表示，已經確定了所有距離根節點不超過i的邊，與根距離不超過i的點集合為s1，恰好為i的點的集合為s2，此時已經出現的邊的貢獻和的最小值。

轉移時，需要枚舉與根距離恰好為i-1的集合s3，從dp(i-1,s1-s2,s3)轉移過來。

啊啊啊大巴到服務區了，等會兒再更。

嚶，以上的做法就是O(n * 4^n)，複雜度請自行分析。

接下來是O(n * 3^n)的做法。

dp(i,s)表示，已經確定了所有距離根節點不超過i的邊，與根距離不超過i的點的集合為s，此時所有已經確定的邊的貢獻和的最小值。

因為我在大巴上睡了一覺，發現s2是不用記的。在原來的做法中，只有s2中的點能夠向距離i+1的那一層連邊，然而讓整個s1都能向第i+1層連邊也無傷大雅，因為讓s1-s2中的點連向第i+1層，這些邊的貢獻乘上了i+1，是偏大的，並不是最優的，同時，這麼做也不會漏掉真正的答案。

T3：phalanx

這個文件名的單詞我不認識，考場上打成了plalanx，直到最後一刻才發現，咳，嚇死我了（逃

咳咳，說正經的。

我們來考慮，一個人(x,y)出列再歸隊後造成了哪些變化。

對於所有i(y&<=i&

對於所有i(x&<=i&

以及，原來在(x,y)的人走到了(n,m)

怎麼維護？

考慮n=1時的簡化版本。

一個長度為n的序列，每次選出一個人，把它刪掉，它右邊的人都朝左挪一格，最右邊空出來的一格填上一個新的人，問每次出列的人的序號。

這非常簡單，線段樹，樹狀數組都能做。

推廣到這道題上怎麼做呢？獨立維護：

第1行的前m-1個

第2行的前m-1個

...

第n行的前m-1個

以及，最後一列。

對這n+1個子問題獨立計算出答案。

每行的前m-1個的子問題中，右邊新補的人來自最後一列。

最後一列的子問題中，下面新補的人是(x,y)，是答案。

說完了。

update 2017.11.15

據d2t3的出題人透露，線段樹被卡掉了，樹狀數組才能過。

線段樹的常數也沒有大得過分啊？這都要卡掉就很壞了啊:)

T1這種題唯一的作用就是增加高水平選手翻車概率並且讓找規律選手過掉吧...

update 11.14: 中老年選手最後一年OI了..認真寫一下吧

Day1:

T1. 給定兩個數，求最大不能被線性表示出的數，即 $c = ax+by, x, ygeq 0$ 。

解法： $ab-a-b$ 。

如上所述，我認為這個題不應該出現在NOIP這種正式的比賽中。從實際情況來看，很多水平不高的選手用打表，甚至看樣例找規律的方法三分鐘做出了這個題，而中等水平的選手嘗試去推式子而一個多小時肝不出來，很難起到正確區分選手能力的作用。

T2. 計算時間複雜度的大模擬

老年選手居然少判斷了一種情況...

雖然很不清真但是也不能說這題怎麼樣..畢竟代碼能力也算考核的重要指標..

T3. 給定一個有向圖，問從 $1 ightarrow N$ 長度在 $[d, d+K]$ 範圍內的路徑有多少。 $d$ 為最短路長度。

解法：考慮動態規劃。設 $f[nd][k]$ 為 $1 ightarrow nd$ ，長度為 $dis[1, nd]+k$ 的路徑的條數。則方程為：

$f[nd][k] = sum_{j ightarrow nd} f[j][dis[nd]+k-dis[j]-g[j][nd]]$

這個狀態設計的拓撲序為第一關鍵字為 $k$ ，第二關鍵字為 $d+k$ 對應的分層圖中的拓撲順序。如果某一個分層圖中帶環，則答案為無窮大。

具體實現可以用分層拓撲排序+dp實現，也可以用記憶化搜索。事實上用記憶化搜索更加便於實現，特別是對帶環情景的判斷（雖然常數可能不太優越）。

總體來看，有一道不知所云的題目(T1)，整體思維難度也遠不及NOIP2016，但處理細節比較多（對老年選手很不友好啊

Day2:

T1. 一個有若干球形空洞的乳酪，問上表面和下表面是否聯通。

良心送分，並查集或者bfs都可以。

兩個坑點：

可能會爆long long。這個問題可以用把 $x^2+y^2+z^2leq 4r^2$ 改寫為 $x^2+y^2leq 4r^2-z^2$ 來規避掉。也可以直接ull處理。
可能有圓心 $<0, >h$ 的情況。要特殊判斷一下。

T2. 給定一個點數 $le 12$ 的無向圖，求一個有根生成樹，使得 $sum_i d_ie_i$ 最小， $d_i$ 為深度， $e_i$ 為連接一個點和其父親的邊權。

考慮狀壓dp。設 $f[i][S_1][S_2]$ 為第 $i$ 層，總共 $S_1$ 中的點被訪問過， $S_2$ 為第 $i$ 層的點集合。由於 $S_2subseteq S_1$ ，總的狀態數是 $O(3^n)$ 級別的。那麼只要預處理出兩個集合的最大匹配（也用狀壓dp，選出一個點枚舉他的選擇集合），就可以在總的轉移代價為 $O(n4^n)$ 內解決了。

（好像 $S_2$ 沒必要設計在狀態裡面，預處理的時候稍加操作就可以 $O(n3^n)$ 了。不過實測 $O(4n^n)$ 跑得飛快。

T3. 給定一個矩形方隊，有若干個出隊操作，問每次出隊的是幾號。

考慮對每一行和最右邊一列用一個數據結構維護一下出隊人的編號，對於一個出隊操作，如果是沒出過隊的人，用二分找到位置，否則去數據結構里找對應位置的人。

顯然可以用splay維護。（雖然我沒寫完（然後淪為暴力選手

正解是樹狀數組吧..貌似和某一場VK Cup的B題很像..（那個題我當時就是splay強上的

Day2題目相對比較合理，T1是演算法入門題，T2是比較麻煩的狀壓（說到底還是套路題）。比較有亮點的就是T3，標誌著log數據結構正式進入NOIP。

就是這樣2333

---------update 11.21-----------

答主D1T2 FST了...

已更新Day2

Day1

劉潤達：關於即將到來的NOIP2017，你怎麼看？

你們這個T1啊，出的真是excited。

考場上看完題只有兩個想法：

T1怎麼做啊？

T2不要寫掛啊。

啥？T3？不可能會的。30分暴力敲完走人。

於是我這種數學渣渣花了1h推T1的式子發現推不出來，然後花了20min敲了60分的exgcd，最後花了10min打了打表並發現規律。

所以T3根本沒怎麼仔細想，時間都花在T1上面，還有檢查T2，總是怕寫掛。講道理如果不在T1卡90min我應該能T3做出來70的。。。

最後T3的30分掛在了n=p=1的點，這種情況我會輸出1而不是0，平常打CF的時候都很注意結果這次掛了。。。

Day2

T1良心送分！可惜我爆了longlong。平常打CF都是很仔細的算會不會爆longlong，結果今天太緊張忘了算了。。。（考場debuff太嚴重。。。）

T2挺神的。想了半天狀壓結果不會，而且覺得T3可做，就果斷打了70分搜索。

T3是好題！給劼爺好評！在比賽最開始的時候寫了30分暴力，後來剩70min的時候繼續補T3，想到了80分演算法，然而寫完50分並拍完之後只剩15min了，最後線段樹沒寫完遺憾GG。

這次NOIp最能體現我的實力的地方可能就是D2T3的80分演算法了，結果還是因為自己弱沒打完而再一次淪為暴力選手。。。

stdcall：關於即將到來的NOIP2017，你怎麼看？

祝賀一個log系列數據結構正式進入NOIp考點，順便再次感謝劼爺的D2T3。

不請自來，占坑

UPDATE：來寫了

第一天第一題看完我愣了一會，說實話並沒有想到NOIP第一天第一題會考「會不會編程」之外的東西，雖然這個題無論從數論還是組合還是找規律意義上來看都非常的容易，但依舊超出了大多數初學者的能力範圍（沒有打表-&>猜想-&>證明的意識）。

第一天第二題是一道很無腦的模擬題，沒什麼好評價的，主要考察棧的使用，還是裸模型的那種，其實一二兩道題互換或許是更好的排題方式。

第一天第三題的難度超過了以往的第一天第三題，除了考察使用超出最短路限制K對最短路做reduce以減少狀態之外，還考察了non-trivial的DP順序（需要對0權邊做topo-sort來確定），應該是相當有綜合且有區分度的題目了。不知道選手做的如何。

第二天第一題考察的是極其簡單的dfs判連通性的知識，難度合適其他沒什麼好說的。

第二天第二題需要掌握either枚舉子集的轉移方式or3進位狀態壓縮狀態表示，我考前是沒想到狀態壓縮能考這麼難的。除了狀態壓縮DP這個經典模型之外，原題到模型的轉換也是不簡單的，需要想到按照距離從小到多填和每次填一層記錄層數或者填一個記錄哪些點在當前層，這兩種做法都需要在確定階段後壓縮狀態（去掉不用的信息）。不論去年D2T3轉移優化的步驟，近年D2T2甚至還要難一些。從選手反饋來看不以NOI為目標作為訓練的選手表現並不理想。

第二天第三題是比較套路的數據結構題，從操作拆解轉化為線段樹操作，再轉離線用線段樹解決。雖然不算難但數據結構中幾個經典的思想都有涉及。很多NOI以上級別選手看著可能無聊，但對於NOIP以上集訓隊以下選手來說其實是一道綜合性區分度都不錯的好題。

總體評價待更：

簡要評價：思維難度低，細節、常數、代碼難度高。

D1T2是很裸的模擬，然而細節有點多。

D1T1如題目名稱，是個數學題，很多人都推出來了。

D1T3的最短路和DP比較顯然，難點在0權環的處理，細節容易炸。本人寫了記憶化搜索，本機極限數據要4.5s，估計只能70分。

D2T1簡單的判連通性，不知道數據類型坑不坑人。

D2T2暴力分很多，以及看數據範圍可以想到狀壓DP，容易拿分。

D2T3大數據結構，本人的實現方法是用Trie維護每行的原始部分，用線段樹維護每行的新增部分及最後一列，空間複雜度多log。（標算是離線樹狀數組，可惜本人想到了離線卻沒想到逐行處理是對的）這題我花了1h寫代碼及對拍，碼長2K。

集訓隊群不少選手表示題目比較無腦。本人感受是，除D2T3外剩下5題基本上看完就會了，D2T3想一下x=1怎麼做很快也就會了，然而D1T2和D1T3的細節查了好久，D1T3還被卡常數，感覺很虛。

Day1

首先感謝艾教（往下看就知道咋回事了）

T1一眼數據範圍以為是logn複雜度，壓根就沒想著去推結論

exgcd推了一個多小時沒出來，心態炸崩

然後趕快打了個30分去做T2T3

T2大模擬還好（多虧寫過一邊魔獸世界改hhh）

T3沒時間了只騙了k=0的分

最後還剩25分鐘左右的時候，把該打暴力和騙分的都打完了，然後轉戰T1

可是推不出來我能咋辦呢（攤手）

然後對著屏幕發獃

想著自己大概要退役了吧

自己大概省一都拿不到了吧

有點不甘心。。。

艾教說過T1掛了可是要打手的（開玩笑）

要是艾教的話肯定會這麼說：

T1都能掛！

T1這麼水隨便猜個結論就出來了！！！

然後我瞥了一眼屏幕繼續發獃。。。

等等。。。woc啥？！

21 - 3 - 7 = 11 。。。！！！

另一個樣例是啥來著。。。30 - 3 - 10 = 17 ！！！

再試試別的數據。。。

卧槽！！！（感覺自己要上天）

再次感謝艾教。。。託夢？

最後祝機房的你們明天rp++

六道題中，D1T2 D1T3 D2T1 在代碼實現以及邊界上有許多的細節，稍有不慎便全盤皆輸；而這些題的思維難度都不大。私以為，NOIp 2016 的更有思維難度，而不是更有代碼難度和細節難度的小清新思路題畫風可能更加適合 NOIp，今年的這種細節題可能更適合其他比賽。

同時，希望出題人能夠在題面上走點心。部分題目題面和排版都很像粗製濫造的 NOIp 模擬賽，甚至我覺得比某些模擬賽的排版還差一點。畢竟 NOIp 是大多數 OIer 的最後一戰，還是希望能夠讓 NOIp 在各個環節都更加正式。

NOIp 第一次出現了 log 級數據結構作為標算，以後 NOIp 選手的數據結構水平的要求應該會高很多啦。

我怕是沒上過小學的人

UPD: swap(day1, day2);

Day1

T1: 找規律或成為最大贏家

T2: 得模擬者得天下

T3: 似乎有wys的味道？(劃掉

Day2

T1: 看似是個玄學搜索

T2: N=12，生成樹有點美滋滋啊（事實上是狀態壓縮dp）

T3: 有種2015年(也有可能是2016?)計蒜之道的感覺...splay是不是可以做？

UPD1@2017.11.13: 在洛谷上手糊了一波，發現只搞到490。我認慫了。

來蹭個熱度

在下今年有幸監考了GD的NOIP

在賽場上見到了一個被OI耽誤的天才畫家

?(?)?

監考的時候看到D1的題，一度覺得T1是三題裡面最難的。因此收穫多個白眼…

謝邀

T1熟知結論..我似乎是小學五年級知道的（霧

T2模擬

T3一個div1C難度的題..但有一些代碼量

總體說來比去年簡單吧..

花了30min打完了前兩道，第三題卻寫了整整2h..

八十中的電腦卡得懷疑人生~(&>_&<)~

敲一行代碼半天才能載入出來，50*200000的for循環要跑好幾秒

根本測不了速..

最後浪了一個小時..

感覺藥丸？

就當是為CMO積攢人品了O(∩_∩)O~

DAY2

T1 暴力

T2 DP

T3 數據結構

T1開考切掉（KDtree好像不在考綱里？）

T2感覺還是挺有意思的

大暴力是n^3 * 4^n的

優化一下就能達到n * 4^n

各種錯，近一個小時寫完了

看T3

本來想寫個80分就棄的，然而某幾個點好像要手寫hash？

然後就懶得寫部分分了

花1h左右寫了個線段樹，本機速度還行，不知道會不會被卡..~(&>_&<)~

稍微檢查了一下，還剩一小時

感覺T2有點虛，稍微想了想發現可以n * 3^n

二十分鐘後過掉了樣例

之後一直無所事事地在走廊里走來走去

總體難度不算太大吧

感覺第二天T2還比較有意思？（可能是我做題太少了）

兩天T3都卡常真是報警..

UPD：啊對了我貼一下題解吧

T1 ab - a - b

T2 模擬，寫個棧記錄一下就行

先求出來每個點到起點和終點的最短路徑長

記dp[i][j]為從1到第j個點長度為最短路徑+i的路徑數

只需求出dp[0][n]+...+dp[k][n]

按i從小到大更新dp，同一i按到1號點從近到遠更新，如果距離相同，按所在極大強聯通分量的拓撲序更新

縮點時順便判一下-1

T1 BFS

記dp[a][b]為當前深度為a，b集合中的點都被訪問過時最小還需多少花費

用n^2 * 2^n 預處理每個集合到每個點的最短距離

即可用n * 3^n預處理出每個集合到每個與其不交集合的最短距離

那麼就可以用3^n*n完成所有dp值的計算了

只需支持一個單點查詢，單點刪除，末尾加數的數據結構

我寫的線段樹

堅決反對T1這種區分度不大並且不能正確區分選手的題目進入Noip。

私以為選手可大致分為以下實力遞增的 5 檔：

1.非常弱，直接暴力走人。

2.數論上來先打表，發現規律，直接A掉T1，但是能力不足以寫出後面的題目。

3.有一定的基礎，嘗試推出T1的擴展歐幾里德做法，但推不出來，只好交暴力，但其實力足以A掉T2。

4.有一定的基礎，並且能用數學方法推出T1的做法，但因推T1浪費時間過多而導致T3拿比較低的分數。

5.上來秒掉T1，然後花足量的時間A掉T2T3。

所以說，得分並不能很好的表現出選手的實力（特別是中間層次），所以T1不應該出現在NOIp。

我，noip2017，退役。

感覺出的不比去年好。

update：那我改成稍微不友善的措辭吧，day1題出的很辣雞。

T1的滿分演算法是和編程關係不大的而且還可以打表。

T2隻是一道模擬題。

T3有些卡常。

update：

考完day2了，稍微比day1有腦一點。

T1是個簡單題，有細節然而不卡。

T2不知道是不是我腦迴路和大家不一樣，看完題和數據範圍的那一刻我就想到n*3^n了，因為這個題的思考方向肯定是狀壓，階段容易劃分（一層一層來），只要意識到並不需要管是不是嚴格第i層就好了。感覺簡單無比？

T3x=1很簡單，也容易推廣，也是思維難度不算大的題。

最後感覺確實沒有去年給我的那種題目難度適宜，noip畫風內讓你感覺idea小清新且巧妙，檔次和區分度都良好的感覺，考前認為今年noip會更毒，現在卻有點失望。

比較悲傷的還是，大家都認為簡單的d1t1還坑了我校一些高水平選手。

各位出題人能不能照顧下在考場上很無聊的人啊qaq……

什麼都不想干……好煎熬啊……

作為退役選手，我對今年 NOIP 題目比較滿意。

D1T1 偏難，考察選手對數據分析的能力。相對於近年的 D1T1，不太適合初學者。作為有經驗的 NOIP 選手或 NOI 選手，應該能輕易找到規律。這道題不適合放到這個位置，但他是一道好題，把它放到 D2T1 可能更合適一些。

D1T2 難度適宜，比去年的天天愛跑步好很多。考察對時間複雜度的理解與基礎編程能力，對於語言基礎較好的選手可以輕易得到滿分。對語言基礎一般的選手也有一些部分分。

D1T3 難度適宜，考察圖論、動態規劃的綜合能力與對題目的分析能力。實現較複雜，對代碼能力有一定要求。我不會。

D2T1 難度適宜，考察坐標的運用與圖的連通性判定。對初學者可能比 D1T1 更容易得到滿分。

D2T2 難度不清楚，我不會，但部分分設計的很好。我寫了枚舉生成樹的 70 分，感覺是一道思路題，老年選手甘拜下風。

D2T3 難度適宜，數據結構進入 NOIP 不是什麼奇怪的事 —— 數據結構是中國選手的一大優勢，雖然我不會這題，但我對普及數據結構是很支持的。

另外，反對一些人因為自己不會某題而噴某題。我感覺我足夠客觀地在評價了。

day2:

將距離小於等於r的連邊，然後bfs或者並查集得到上下邊界的連通性即可。

時間複雜度O（T*n*n）。

注意這道題有一個坑點：比如有兩個點的坐標是（1e9，1e9，1e9）和（-1e9，-1e9，-1e9），那麼在計算兩點距離的平方時會得到1.2e19，這超過了long long的存儲範圍，要用unsigned long long。（upd：題面隱含條件z非負，那麼距離的平方最大為9e18在long long存儲範圍內）

另外如果使用並查集只寫路徑壓縮的話可能被1kw次操作卡掉。（upd：只寫路徑壓縮的複雜度為O（nlogn+n^2）不會有問題）

設f（i，S，S2）表示已經分配了深度小於等於i的節點集合為S，深度等於i的節點集合為S2的最小代價，轉移時枚舉一個S的超集S3讓其成為深度為i+1的節點與S2集合里的節點連邊，預處理一下轉移數組就可以O（1）計算轉移的代價。

對於時間複雜度的一個初步分析約為n*（3^n*C(n,1)+3^(n-1)*C(n,2)+...+1）=O（n*4^n），然而我們不難發現合法dp狀態中|S-S2|&>=i-1（即每種深度最少要放置一個節點），實際遠遠小於理論分析上界。實測當n=12時轉移次數大約為3kw左右。

考慮用splay維護每一行的第一列至第m-1列以及全體的最後一列，每次操作相當於在序列中查詢一個位置，刪除一個位置，在序列最後加入一個元素。直接維護的話是n*m個節點，但我們注意到初始每一行是一個等差數列，就可以用n+m+q個區間節點來維護了。

時間複雜度O（qlogn）。

由於操作的特殊性（只在末尾插入）可能有更簡單的方法（

三道毫無營養毫無區分度的題目。

退役選手來NOIP划水

Day1

T1找規律幾秒鐘找完切了

T2模擬隨便寫了寫

T3 寫了70分退役選手代碼能力太弱

Day2

T1隨便寫了寫

T2不會敲爆搜 10min敲完

T3 忘了splay怎麼寫 30分暴力 5min敲完

打了兩個多小時掃雷，提前30min離場。

幸虧我tm高三了...

Upd：竟然全省rank5 震驚

這個day1怎麼說了，這可能是我在所有模擬賽裡面做過最順暢的了。

考試前一天晚上告訴自己不要緊張，目標是省三的話還挺管用的。

t1:這應該是很水的結論題了吧，第一眼沒看出來，在草稿紙上隨手推了一下就出來了，但好像方法和別人不太一樣的說，結果後來對拍打了一個小時(尬)。聽說很多人推了兩個小時的ex歐幾里得沒有推出來？！！

t2:我真的是高估今年題目的難度了，看到第二題題面著實被嚇了一下啊，於是我居然棄掉了(好後悔好後悔)，就打了個30分的，細節挺多的，準確來說我一點也不喜歡模擬題。

t3:光前面就花了我好多時間了，棄掉。

今天做題策略不好啊，今年的題對於我這種初二小蒟蒻來說是有點簡單的(相比往屆和模擬賽)

不忘初心方得始終

我可能把t2的yes和no的全大寫了

//------------------------------

順便問一句高考怎麼補啊