保齡球游戲的獲勝者

【模擬】按題意模擬。

找出疊涂元素

【預(yù)處理 + 計(jì)數(shù)】先預(yù)處理，用pos數(shù)組記錄mat[i] [j]在mat中的位置。然后遍歷arr[i]，用兩個(gè)數(shù)組row_cnt和col_cnt記錄每行每列的涂色個(gè)數(shù)，如果某行或某列被涂滿了就返回i。

前往目標(biāo)的最小代價(jià)

【Dijkstra】答案是start、target和特殊點(diǎn)構(gòu)成的有向圖上，start到target的最短路，用Dijkstra計(jì)算最短路。

字典序最小的美麗字符串

【貪心】長(zhǎng)度為2的回文串就是兩個(gè)相鄰的相同字符，長(zhǎng)度為3的回文串就是下標(biāo)之差為2的兩個(gè)相同字符。因此一個(gè)字符串是美麗的，當(dāng)且僅當(dāng)其中的每個(gè)字符與它前面兩個(gè)字符都不相同。為了找到比s大的，同時(shí)又是最小的美麗字符串，先從最后一個(gè)字符s[-1]開始修改。因?yàn)榇鸢敢萻大，所以只能讓s[-1]變大，且變化后不能和s[-2]以及s[-3]相同。如果能在字母表前k個(gè)字符中找到符合要求的字符，那么只要修改s[-1]就行了，否則還得修改s[n-2]。因?yàn)榇鸢敢萻大，所以只能讓s[n-2]變大，且變化后不能和s[n-3]以及s[n-4]相同。從上述分析可以看出來，修改每個(gè)字符的流程都是一樣的：如果要修改s[i]，可以首先枚舉字母表的前k個(gè)字符，看能否找到比s[i]大，但又和s[i-1]以及s[i-2]不同的字符。如果找到了即可結(jié)束流程，否則還得修改s[i-1]，重復(fù)上述流程。如果已經(jīng)改到s[0]還無法滿足要求，那就是無解。如果修改s[i]就能滿足要求，由于s[]已經(jīng)比原來大了，后面的字符不管填什么，答案都會(huì)比s大。因此s[i+1]到s[n-1]只要貪心地填入與前兩個(gè)字符不同的最小字符即可。因?yàn)閗≥4，總能找到這樣的字符。