統(tǒng)計(jì)鏈表奇數(shù)節(jié)點(diǎn)

【一次遍歷】遍歷即可，小技巧是ans直接加0/1結(jié)果，省去if判斷這一步。

光線反射

【模擬】用DIRS數(shù)組存↑↓←→（對應(yīng)0123四種狀態(tài)）。由題意，碰到向左傾斜的鏡面，←↑是一對，↓→是一對，可以通過異或操作來轉(zhuǎn)換兩種狀態(tài)（狀態(tài) xor 2 即可，總共0123四種方向，0 xor 2=2，2 xor 2 = 0，1 xor 2 = 3，3 xor 2 = 1）；碰到向右傾斜的鏡面，↓←是一對，↑→是一對，同理，狀態(tài) xor 3。初始x,y = (0,0)，d = 1即DIR = (1,0)，然后開始模擬。

整理書架

【單調(diào)?！恳蟠螖?shù)盡可能少，所以要把所有出現(xiàn)次數(shù)大于limit的元素，刪除知道出現(xiàn)次數(shù)=limit。要求字典序最小，所以從左往右遍歷如果找到更小數(shù)字就把前面更大的數(shù)去掉。用單調(diào)棧模擬，遍歷的同時，要保證棧里的元素出現(xiàn)次數(shù)不超過limit，如果后面沒有足夠的元素，也不能讓元素出現(xiàn)次數(shù)低于limit，如果遇到比棧頂小的元素，可以出棧。代碼中，入棧時候要看后面有沒有足夠元素。如果沒足夠元素（cnt[x] = limit）就continue，如果棧頂比x大且棧頂 元素也夠則可以出棧。

意外驚喜

【貪心 + 分治 + 01背包】由于題中說每個禮物包里的禮物價值非嚴(yán)格遞增，所以可證不存在選了兩個數(shù)組但都沒有選完的情況，之多只有一個數(shù)組沒有選完，其余要么整個數(shù)組都選，要么都不選。枚舉這個沒選完的數(shù)組，其余的轉(zhuǎn)為01背包（整個數(shù)組和當(dāng)作一個物品的價值，數(shù)組長度當(dāng)作物品體積）。為了優(yōu)化時間復(fù)雜度，需要用分治來優(yōu)化。