計(jì)算字符串的數(shù)字和

【模擬】用tmp維護(hù)每輪操作結(jié)果，遍歷字符串s，每k個(gè)字符為一組，計(jì)算該組的數(shù)字和sm，并轉(zhuǎn)換為字符串添加至tmp尾部，最終將s更新為tmp所表示的字符串，模擬操作直到s的長(zhǎng)度≤k，返回ans=s。

完成所有任務(wù)需要的最少輪數(shù)

【貪心 + 哈希表】只有1個(gè)的數(shù)字取不了，盡可能多拿3，如果模3余1，那少拿一個(gè)3拿兩個(gè)2，次數(shù) = x // 3 + 1，模3余1，多拿一個(gè)二，也是 x // 3 + 1，可以寫成（x + 2）// 3。

轉(zhuǎn)角路徑的乘積中最多能有幾個(gè)尾隨零

【維護(hù)各方向的前綴和】尾0的個(gè)數(shù) = min(路徑上數(shù)的因子2的個(gè)數(shù)和，因子5的個(gè)數(shù)和)。那么數(shù)越多越好，路徑起點(diǎn)終點(diǎn)都應(yīng)該在邊界上，預(yù)處理每一行的因子前綴和，枚舉所有路徑，從上往下走，枚舉左轉(zhuǎn)右轉(zhuǎn)；從下往上走，枚舉左轉(zhuǎn)右轉(zhuǎn)。ans = 所有路徑上的Min(s2,s5)。代碼中，c2、c5是預(yù)處理遞推算出每個(gè)數(shù)的因子 2 的個(gè)數(shù)和因子 5 的個(gè)數(shù)，兩層for循環(huán)計(jì)算 grid 每行因子 2 和 5 的前綴和，先從上往下，枚舉左拐還是右拐，再?gòu)南峦?，枚舉左拐還是右拐。

相鄰字符不同的最長(zhǎng)路徑

【DFS】若無(wú)相鄰節(jié)點(diǎn)限制，本題求的就是樹直徑上點(diǎn)的個(gè)數(shù)，用樹形dp求直徑，枚舉子樹x的所有子樹y，維護(hù)從x出發(fā)的最長(zhǎng)路徑maxLen，更新答案為從y出發(fā)的最長(zhǎng)路徑加上maxLen + 1，合并從x出發(fā)的兩條路徑，遞歸結(jié)束返回maxLen。要求相鄰，所以轉(zhuǎn)移時(shí)限制s[y] == s[x]才能轉(zhuǎn)移，求點(diǎn)的個(gè)數(shù)就是最長(zhǎng)路徑的長(zhǎng)度 + 1.