清北金牌教研團隊獨家解析NOIP2016 Day1試題!!!

題目1：玩具

描述好亂. 反正就是一群人圍成圈, 若干次左走右走問最後到哪.

加加減減取模就好了.

水水水水過.

第一題比較簡單就不多做描述啦~

2

題目2 : 跑步

一棵n個點的樹, m條路徑, 問對於每個點, 經過本點且起點距離本點為本點點權的路徑條數.

n,m≤3?105

我感覺這個題有點難呀. 很有可能是我想複雜了.

把每條路徑從lca處拆成兩段.

考慮對於每個點的詢問.

對於起點到lca這段, 詢問就是詢問子樹里lca深度小於等於當前深度的深度剛好為某個值的路徑起點個數.

對於lca到終點這段, 詢問就是詢問子樹里lca深度小於等於當前深度的 (長度-深度) 剛好為某個值的路徑終點個數.

然後就成了一個比較簡明的數據結構問題.

一種思路是平衡樹啟發式合併, 但是時間可能會炸.

另一種思路是用dfs序式樹鏈剖分, 每條路徑會被拆分為不超過lg個dfs序上的子段. 在路徑的每個子段的起點和終點處分別打上標記. 然後對dfs序進行一次掃描即可得出答案. 複雜度比較優.

3

題目3 ：換教室

n節課, v間教室. 每節課有兩種教室位置選擇, 其中一種是已定的. 你有m次機會申請換掉其中一節課的教室位置, 每個請求有獨立的p的概率成功. 教室在一張圖上, 求最小總奔波路期望.

n,m≤103,v≤3?102

個人認為這題比上一題水.

先用floyd處理出任意兩間教室間的最短路.

然後用dp.

fi,j,k 表示前i間教室, 用了j次交換機會, k表示上一次有沒有換. 存答案.

轉移就是一個概率的算式, 較為簡單. 略.