OI常見解題思路大匯總【不定期更新】

典例

JZOJ 6433. 【NOIP2019提高組正式賽day2】Emiya 家今天的飯&題解

型別

• 若干種中每種選取若干個， 保證每種不超過總數的一半的方案數，

思路

• 如果直接考慮遞推轉移，需要實時維護每種選擇的個數，才能保證滿足條件，
• 但是可以想到，若有某種超過了一半，其它的則不可能超過一半，用總方案數減去不合法的，列舉哪一種超過了一半，需要記錄當前選了多少個，以及不合法的這種選擇了多少，
• 還可以繼續優化，因為總數不確定，不妨不記錄總數，而記錄不合法減去合法的個數，最后大于 0 0 0的部分說明不合法的超過了一半，

典例

JZOJ 6439. 【GDOI2020模擬01.17】小 ω 數排列&題解
JZOJ 4345. 【WC2016模擬】Fountain

型別

• 求相鄰兩數之間滿足某種條件的排列方案數，

思路

• 考慮用DP依次加入每個數，不需要管當前已經加入的數構成的排列如何，可以只記錄當前狀態下的構成的“段數”，（因為題目限制只和相鄰兩數有關，所以已經被包含在中間的部分對后面沒有影響）
• 每次加入時考慮自成一段、加在某一段的某側、加在某兩段中間并將他們合并.
• 如果題目有需要，可能還需要考慮是否加在最后整段的邊界上（邊界個數只可能為 0 / 1 / 2 0/1/2 0/1/2）

典例

JZOJ 3583. 【GDOI2014模擬】小A的樹

型別

• 若干區間中數的位運算，可以推廣到樹上路徑中的位運算，

思路

• 如果是加法或乘法，那么可以直接維護前綴和/前綴積，位運算不像加法和乘法，可以通過逆運算減法和除法得到特定的值，
• 但是如果拆位來看，與運算一定是前面一段連續的 1 1 1和后面一段連續的 0 0 0，或運算反之，這樣就很好維護，最后再把每一位的答案加起來，

典例

JZOJ 3457. 【NOIP2013模擬聯考3】沙耶的玩偶(doll)

型別

• 某種連邊方式下，最小的路徑條數覆寫所有點，每個點只能被一條路徑覆寫，

思路

• 這種題可以反著想，最初每個點自成一條路徑，每連一次路徑條數減少 1 1 1，那么合并的次數越多，路徑條數越少，
• 把所有的點分成入和出兩邊，能連邊的兩點之間出入連上，跑一邊二分圖最大匹配，用總點數減去最大匹配即為答案，

典例

JZOJ 5963. 【NOIP2018提高組D1T3】賽道修建

型別

• 樹上符合特定條件（如路徑點數、邊權和達到某個值）的最大路徑條數，每個邊只能被一條路徑覆寫，

思路

• 從葉子節點往上做，到每個節點時，它的每個兒子會各自從下方延伸了一條尚不符合條件的路徑到它（若符合條件，可以直接斷開，答案加 1 1 1），
• 盡管路徑再多，能繼續向上延伸的也只有一條，剩下的在當前節點處兩兩匹配從而使它們盡可能多的對答案有貢獻，
• 以最優的方式匹配完，然后剩余的中選擇最優的（如果沒有則從該節點直接延伸）向上延伸，
• 同時要注意雖然是以最優的方式兩兩匹配，但不能保證向上延伸的方案一定最優，最后還要重新掃一遍判斷是否能有更劣卻同樣滿足條件的匹配，使得延伸上去的路徑更優，

典例

JZOJ 6809. 【2020.10.29提高組模擬】不難題&題解

型別

• 二維或多維空間中每個維度只能向某個方向走，其中若干點不能經過，求到達某個點的方案數，

思路

• 容斥，設 f i f_i fi?表示只經過了第 i i i個不能經過的點的方案數，用到達它的總方案減去其它 f j ( x j ≤ x i , y j ≤ y i , . . . ) f_j(x_j \leq x_i,y_j\leq y_i,...) fj?(xj?≤xi?,yj?≤yi?,...)，
• 把終點也視為一個不可經過的點，最后答案就是終點的 f f f值，

典例

JZOJ 6808. 【2020.10.29提高組模擬】easy&題解

型別

• 序列上統計符合某條件的區間個數，條件與區間最大值和最小值有關，

思路

• 這種題沒有特別固定的解法，但大致可以用這種套路做，
• 列舉區間左/右端點，順著或倒著掃一遍，用資料結構實時修改，并查詢答案，
• 最值的修改可以用單調堆疊，彈堆疊時在資料結構上修改，

典例

JZOJ 6813. 【2020.10.05提高組模擬】送信
JZOJ 6276. 【noip提高組模擬1】樹 &題解

型別

• 樹上路徑與經過點對的統計，

思路

• 考慮經過一個點對的條件，分兩點為祖先關系或無祖先關系套路，用dfs序來看則可以轉化為二維/三維偏序問題，

典例

型別

思路