最好的撲克手牌

【模擬】

全 0 子數(shù)組的數(shù)目

【遍歷】考慮每個(gè)以0結(jié)尾的子數(shù)組的個(gè)數(shù)。統(tǒng)計(jì)連續(xù)0組成的長(zhǎng)度c，每個(gè)c可以貢獻(xiàn)c個(gè)子數(shù)組。

設(shè)計(jì)數(shù)字容器系統(tǒng)

【有序集合】 整體思路：雙向映射, i2n → {idx: number}; n2i → {number: idx}

【懶刪除堆】對(duì)于change操作，直接往ms中記錄，不做任何刪除操作；對(duì)于find操作，查看堆頂下標(biāo)對(duì)應(yīng)的元素是否和numbe相同，若不相同則意味著對(duì)應(yīng)的元素已被替換成了其他值，堆頂存的是個(gè)垃圾數(shù)據(jù)，直接彈出堆頂；否則堆頂就是答案。

不可能得到的最短骰子序列

【哈希集合】數(shù)組中長(zhǎng)度為m的序列都能找到的前提是，數(shù)組中存在一個(gè)前綴，該前綴中長(zhǎng)度為m-1的序列都能找到，且在該前綴之后的子數(shù)組中所有的點(diǎn)數(shù)均出現(xiàn)過(guò)至少一次。

【貪心】考慮包含1到k的最短前綴，無(wú)法得到的子序列的第一個(gè)數(shù)必然在里面。這個(gè)前綴的最后一個(gè)數(shù)x，在前綴中只會(huì)出現(xiàn)一次。我們可以取x當(dāng)做子序列的第一個(gè)數(shù)。去掉這個(gè)前綴，考慮下一個(gè)包含1到k的最短前綴。子序列的第二個(gè)數(shù)必然在這個(gè)前綴中。同樣地，取前綴最后一個(gè)數(shù)當(dāng)做子序列的第二個(gè)數(shù)。不斷重復(fù)這一過(guò)程，直到剩余部分無(wú)法包含1到k時(shí)停止。設(shè)取到了m個(gè)數(shù)，對(duì)應(yīng)著rolls的m個(gè)子段。由于每一段都包含1到k，rols必然包含長(zhǎng)度為m的子序列：每一段都選一個(gè)元素即可組成這樣的子序列。因此答案至少為m+1?？梢詷?gòu)造出一個(gè)長(zhǎng)為m+1的子序列，它不在rolls中：前m個(gè)數(shù)分別取各個(gè)子段的最后一個(gè)數(shù)，第m+1個(gè)數(shù)取不在剩余部分中的數(shù)。因此答案等于m+1。