合并兩個(gè)二維數(shù)組 - 求和法

【哈希 + 排序】按題意模擬。

【歸并排序（雙指針）】

將整數(shù)減少到零需要的最少操作數(shù)

【暴力】每次將n減去離他最近的一個(gè)二次冪數(shù)，對abs(n - 這個(gè)數(shù))進(jìn)行重復(fù)操作，直到n為0。 離n最近的二次冪數(shù)為pow(2, round(log2(n)))。

【記憶化搜索】變成0就是二進(jìn)制位都是0，暴力判斷，二進(jìn)制位最右邊的1（低位1的修改影響到了高位），是加1還是減1（加1能進(jìn)位，減1就很普通）。判斷x是2的冪次——x & (x - 1) == 0。

【位運(yùn)算 + 貪心】優(yōu)先消除最低位的1，設(shè)它對應(yīng)的數(shù)字為lowbit，消除方法是加上lowbit或減去lowbit。如果有多個(gè)連續(xù) 1，那么采用加法是更優(yōu)的，可以一次消除多個(gè) 1；否則對于單個(gè) 1，減法更優(yōu)。

【位運(yùn)算 + 找規(guī)律】對于多個(gè)連續(xù)1，如果它和前面的1被至少兩個(gè)0隔開，那么就需要先加上lowbit產(chǎn)生單個(gè)1，再減去lowbit去掉這個(gè)1，需要操作兩次。注意到n ⊕ 3n剛好可得到兩個(gè)1，對于單個(gè)1，n ⊕ 3n剛好可得到1個(gè)1，所以ans = n ⊕ 3二進(jìn)制中1的個(gè)數(shù)。

無平方子集計(jì)數(shù)

【0-1背包】將無平方因子數(shù)的數(shù)字記作SFI，對于每個(gè)[2,30]內(nèi)的SFI，預(yù)處理得到對應(yīng)的質(zhì)數(shù)集合，用二進(jìn)制表示（從低禱告第i個(gè)比特為1表示第i個(gè)質(zhì)數(shù)在集合中，如3,5表示為110，2是0，3/5是1）把每個(gè)SFI的nums[i]轉(zhuǎn)換成對應(yīng)的質(zhì)數(shù)集合，題目就變成選一些不相交的質(zhì)數(shù)集合，他們的并集恰好為集合j的方案數(shù)。

【子集狀壓DP】枚舉mask的補(bǔ)集cs的子集j，有f[j|mask] += f[j]·cnt[x]，其中x是mask對應(yīng)的SFI，cnt[x]是x在nums中的出現(xiàn)次數(shù)。

找出對應(yīng) LCP 矩陣的字符串

【構(gòu)造 + DP】構(gòu)造方案：1.初始化長為n的字符串s，初始化所有s[i]為0，初始化待填入字母c為‘a(chǎn)'；2.找到第一個(gè)\0的下標(biāo)i，把所有j≥i且lcp[i] [j]>0的s[j]填入c；3.c加一，重復(fù)第2步，直到?jīng)]有這樣的i，或者用完了26個(gè)小寫字母（此時(shí)不合法）。構(gòu)造完后需要計(jì)算s的真實(shí)LCP，檢查是否和輸入的lcp數(shù)組完全一致，計(jì)算方式是dp，如果s[i]=s[j]，那么lcp[j]=lcp[i]+[j+1]+1；如果s[i]!=s[j]，那么lcp[i] [j]=0。