最長交替子序列

【分組循環(huán)】外層循環(huán)枚舉子數(shù)組起點(diǎn)，內(nèi)層循環(huán)擴(kuò)展子數(shù)組右端點(diǎn)，時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。

重新放置石塊

【哈希表 + 模擬】每次操作把moveFrom[i]的石塊都移走，按題意模擬。

將字符串分割為最少的美麗子字符串

【DP】由于字符串長度為n，二進(jìn)制值低于2^n，可以預(yù)處理2^n以內(nèi)的5的冪的二進(jìn)制表示，記作pow5。定義f[i]為劃分從s[i]開始的后綴，最少要劃分多少段，枚舉pow_5中的字符串t，設(shè)其長度為m，如果從s[i]到s[i+m-1]與t相等，那么有f[i] = f[i + m] + 1。

黑格子的數(shù)目

【哈希表 + 枚舉】如果(x,y)處有黑格子，那么子矩陣左上角在(x-1,y),(x,y-1),(x,y),(x-1,y-1)都是包含這個(gè)黑色格子的，統(tǒng)計(jì)這些子矩陣中有多少黑色格子。用哈希表vis記錄統(tǒng)計(jì)過的子矩陣左上角，不含黑色格子的子矩陣個(gè)數(shù)是(m-1)*(n-1) - len(vis)。