C題-翻轉(zhuǎn)?

標(biāo)簽：貪心

簡述：如果 S 中存在子串 101 或者 010，就可以將其分別變?yōu)?111 和 000，操作可以無限重復(fù)。最少翻轉(zhuǎn)多少次可以把 S 變成和 T 一樣。

鏈接： 翻轉(zhuǎn)

思路：要求步驟最少->S每個位置最多修改一次->從頭開始遍歷不匹配就翻轉(zhuǎn)->翻轉(zhuǎn)不了就-1

ACcode：

完整代碼：https://download.csdn.net/download/weixin_45741872/89051233

D題-階乘的和???

標(biāo)簽：STL-map

簡述：滿足 m! 為 sum(Ai!) 的因數(shù)的最大的 m 是多少

鏈接： 階乘的和

思路：統(tǒng)計(jì)每個階乘的個數(shù),記錄最小的階乘（記為maxv）。從最小的階乘開始計(jì)算統(tǒng)計(jì)maxv的個數(shù)是否為(maxv+1)的倍數(shù)，如果是則進(jìn)位 比如$3!+3!+3!+3!+3!+3!+3!+3!=8?3!=2?4!$ 相當(dāng)于4!增加了兩個，向上循環(huán)執(zhí)行該操作即可，如果不是那么就可以break了

ACcode：

完整代碼：https://download.csdn.net/download/weixin_45741872/89051233

E題- 公因數(shù)匹配???

標(biāo)簽：數(shù)論-質(zhì)因數(shù)

簡述：找出最早出現(xiàn)兩次質(zhì)因數(shù)的位置

鏈接：公因數(shù)匹配

思路：考慮到 $a_i$ 很小，所以首先預(yù)處理出1 ~ 1000000 所有素?cái)?shù)，然后對于每個素?cái)?shù)枚舉其倍數(shù)，算出每個數(shù)的質(zhì)因子，這里時間和空間復(fù)雜度大概是 $O(loglogn)$，然后對于每個 $a_i$ 枚舉其質(zhì)因子，然后看之前是否有數(shù)有相同質(zhì)因子即可。最后排序輸出答案

ACcode：

完整代碼：https://download.csdn.net/download/weixin_45741872/89051233

F題-奇怪的數(shù)????

標(biāo)簽：數(shù)論-位運(yùn)算

簡述：長為n的數(shù)奇數(shù)位為奇數(shù)偶數(shù)位為偶數(shù)，任意連續(xù)5個數(shù)和不大于m有多少個這樣的數(shù)

鏈接：奇怪的數(shù)

思路：令 $f_{i,a,b,c,d}$ 表示長度為 i 且后四位為 abcd 的奇怪的數(shù)的個數(shù)，初始化時暴力計(jì)算 $f_{5,a,b,c,d}$
f i + 1 , a , b , c , d = ∑ e ≤ m ? a ? b ? c ? d f i