1. 問題引入從一道國賽真題看字符串處理的效率陷阱最近在復盤藍橋杯的歷年國賽真題2020年第十一屆C組的“重復字符串”這道題給我留下了挺深的印象。它初看之下平平無奇甚至有點“送分題”的感覺不就是處理一個字符串讓它變成某個重復子串的多次連接嗎但真正動手實現尤其是想在競賽的時限和內存限制下拿到滿分你會發現里面藏著好幾個關于C字符串操作、算法效率和邊界處理的經典“坑”。很多同學止步于“暴力法能過樣例”卻不知道其算法在特定數據下會超時或者寫出了邏輯正確但冗長脆弱的代碼。這道題的核心場景是給定一個字符串S我們可以進行任意次操作每次操作可以修改S中的任意一個字符。目標是最終將S變為一個“重復字符串”。所謂“重復字符串”是指存在一個長度大于等于1的子串T使得S可以由T重復K次連接而成K是大于1的整數。題目要求我們找到最少的修改次數。舉個例子字符串“abcab”。我們可以把它變成“abcabc”T“abc”,K2這需要修改最后一個字符‘b’為‘c’操作次數為1。也可以嘗試變成“ababab”T“ab”,K3但這需要修改第3個字符‘c’為‘a’第5個字符‘b’為‘b’不變操作次數也是1。題目就是要求這個最小的操作數。乍一看我們需要枚舉所有可能的重復單元長度len_T從1到S.length()然后檢查每個長度下將原字符串對齊到這個重復模式需要修改多少次字符最后取最小值。思路很直接但魔鬼全在細節和效率里。直接無腦枚舉和比對復雜度是O(n^2)當n達到10^5級別時必然超時。這就需要我們深入思考字符串的周期性特征并設計高效的統計方法。2. 核心思路拆解枚舉周期與貪心統計解決這個問題的關鍵在于理解“重復字符串”等價于字符串具有周期性。如果最終字符串是T重復K次那么其長度n必須是len_T的整數倍。對于原字符串S我們假設其長度為n。我們只需要枚舉所有可能的重復單元長度len其中len必須是n的約數。因為如果len不能整除n那么我們無論如何修改字符都無法讓字符串長度n由長度為len的子串整數次重復構成。因此算法框架的第一步是找出字符串長度n的所有正約數。這些約數就是候選的重復單元長度len。對于每一個候選的len我們把字符串S想象成被切分成了k n / len個塊每個塊的長度都是len。我們的目標是修改S使得這k個塊變得完全相同。那么最少的修改次數是多少呢這里就引出了第二個關鍵點列優先統計與多數表決。我們不能簡單地逐個塊去比較那樣效率太低。一個高效的技巧是從“列”的角度來看。我們把這k個塊上下堆疊起來形成一個有len列、k行的矩陣。第j列j從0到len-1就包含了所有塊的第j個字符。例如S “aabbbc”,n6。假設我們枚舉len2那么k3。三個塊是“aa”,“bb”,“bc”。堆疊起來第0列a,b,b第1列a,b,c對于每一列我們的目標是讓這一列的所有字符都變成同一個字符因為只有這樣最終每個塊在這一位置上的字符才相同。那么對于第j列最少需要修改多少次呢答案是將該列修改為出現次數最多的那個字符。假設該列有k個字符其中出現次數最多的字符出現了max_count次那么這一列最少需要修改的次數就是k - max_count把非主流的字符改成主流的。所以對于給定的len總的最少修改次數就是所有len列的這個值(k - max_count)的總和。我們遍歷所有列累加這個值就得到了在這個重復單元長度下的最小操作數。最后對所有合法的len計算出的操作數取最小值就是全局答案。這個思路的精妙之處在于它將一個看似復雜的“讓多個字符串相同”的問題分解為了len個獨立的、簡單的“讓一組字符相同”的子問題并且每個子問題都可以用O(k)的時間通過哈希表統計字符頻率來解決。整個算法的時間復雜度主要取決于1. 求所有約數2. 對每個約數len進行len次字符統計每次統計涉及k個字符。2.1 復雜度分析與可行性證明設字符串長度為n。首先求n的所有約數通常使用O(sqrt(n))的枚舉方法即可。n的約數個數在10^5這個量級下不會太多通常少于200個這部分開銷很小。對于每個約數len我們需要處理len列每列處理k n/len個字符。所以處理一個約數的代價是len * k n。也就是說處理每個約數的復雜度是O(n)那么總復雜度就是O(d * n)其中d是約數個數。在最壞情況下如果n是一個高度合數d可能會比較大但即便如此對于n 10^5d通常也在100量級100 * 10^5 10^7這個計算量在C中是完全可以在1秒內完成的藍橋杯通常1s時限。這比最原始的O(n^2)枚舉好了太多。這里有一個思維陷阱需要避免有人可能會想是不是只需要枚舉len到n/2因為重復單元至少出現兩次。是的K必須大于1所以len必須小于n。但我們的枚舉是基于n的約數約數本身就排除了len n的情況因為K會等于1所以我們只需要枚舉n的真約數大于0且小于n的約數即可。3. 手把手實現從算法到健壯代碼理解了算法我們來看具體實現。我將代碼分成幾個函數使其邏輯清晰便于調試和講解。3.1 第一步獲取所有真約數vectorint getDivisors(int n) { vectorint divisors; // 只需遍歷到 sqrt(n)注意完全平方數的情況 for (int i 1; i * i n; i) { if (n % i 0) { divisors.push_back(i); // i 是約數 if (i ! n / i i ! n) { // 避免重復和n本身 divisors.push_back(n / i); } } } // 注意我們需要的是真約數小于n的所以最后要過濾掉 n 本身如果被加進去了 // 實際上由于我們加了 i ! n 的判斷n本身不會被加入。但為了安全可以再過濾一次。 vectorint properDivisors; for (int d : divisors) { if (d n) { properDivisors.push_back(d); } } return properDivisors; }注意這里有一個優化點。我們其實不關心約數的順序但后續計算中len越小k就越大統計每列字符時循環層數可能外小內大。不過對總復雜度影響不大。確保不遺漏任何真約數即可。3.2 第二步計算給定長度len下的最小修改次數這是核心函數。輸入字符串s和候選長度len返回使其成為重復字符串的最小操作數。int minChangesForLength(const string s, int len) { int n s.length(); int k n / len; // 重復次數 int total_changes 0; // 遍歷每一列 for (int col 0; col len; col) { // 使用數組統計26個小寫字母的出現次數題目通常給定字符集 // 如果字符集更大比如ASCII可以用大小為128的數組或者用unordered_map vectorint count(26, 0); int max_count_in_col 0; // 遍歷該列的所有行即所有塊 for (int block 0; block k; block) { // 計算當前字符在原字符串中的位置 int pos block * len col; char c s[pos]; int idx c - a; // 假設輸入都是小寫字母 count[idx]; // 實時更新當前列的最大出現次數 max_count_in_col max(max_count_in_col, count[idx]); } // 這一列需要修改的次數 總字符數 - 最大出現次數 total_changes (k - max_count_in_col); } return total_changes; }這段代碼清晰體現了“列優先”統計的思想。兩層循環外層遍歷len列內層遍歷該列的k個字符。使用一個固定大小的數組來統計頻率比unordered_map更快前提是字符集已知且不大如26個小寫字母。3.3 第三步主邏輯與邊界處理現在我們把所有部分組合起來并考慮一些邊界情況。#include iostream #include string #include vector #include algorithm #include climits // 用于INT_MAX using namespace std; // 上面兩個函數 getDivisors 和 minChangesForLength 放在這里 int main() { string s; cin s; int n s.length(); // 邊界情況1如果字符串長度小于2它本身不可能成為重復字符串K1 // 但題目可能保證n2不過為了健壯性可以判斷。 if (n 2) { cout 0 endl; // 或者根據題意長度1無法操作輸出0 // 實際上對于n1不存在長度小于n的真約數我們的算法會得到答案0。 return 0; } vectorint divisors getDivisors(n); int min_changes INT_MAX; bool found false; for (int len : divisors) { // len 已經是真約數即 1 len n int changes minChangesForLength(s, len); min_changes min(min_changes, changes); found true; } // 邊界情況2如果字符串本身已經是一個重復字符串那么可能不需要任何修改。 // 我們的算法會枚舉所有約數包括使得 changes0 的那個 len。 // 還有一種情況如果字符串所有字符都相同那么對于 len1 changes0。 // 所以 min_changes 最終會被更新為0。 // 邊界情況3如果 divisors 為空理論上n是質數且大于1那么真約數只有1 // 那么循環不會執行min_changes保持INT_MAX。我們需要處理。 // 實際上對于質數n真約數只有1所以divisors不會為空。 // 但為了絕對安全 if (!found) { // 這種情況發生在 n1 時我們已經提前處理了。 // 如果 n 是質數divisors 會包含1。 min_changes n; // 一個保守的估計或者根據題意處理。 } cout min_changes endl; return 0; }3.4 一個完整的、優化過的示例代碼將上述思路整合并加入一些細微優化比如在minChangesForLength函數中如果某列修改次數已經超過當前全局最小值可以提前剪枝我們得到最終版本#include bits/stdc.h using namespace std; int minChangesForLength(const string s, int len, int current_min) { int n s.size(); int k n / len; int total 0; for (int col 0; col len; col) { int cnt[26] {0}; // C風格數組更快 int max_cnt 0; for (int block 0; block k; block) { char c s[block * len col]; max_cnt max(max_cnt, cnt[c - a]); } total (k - max_cnt); // 剪枝如果當前累計修改數已經超過已知最小值后面就不用算了 if (total current_min) { return total; // 直接返回一個較大的值不影響min比較 } } return total; } int main() { string s; cin s; int n s.size(); int ans n; // 最壞情況每個字符都改也就是n // 枚舉所有可能的重復單元長度 len (必須是 n 的約數且 len n) for (int len 1; len n; len) { if (n % len ! 0) continue; ans min(ans, minChangesForLength(s, len, ans)); } cout ans endl; return 0; }這個版本更簡潔直接將枚舉約數和計算整合在了一個循環里。ans初始化為n最壞情況然后枚舉所有可能的len1到n-1檢查是否為約數如果是則計算并更新答案。minChangesForLength函數中加入了剪枝優化當累計修改數已經超過當前最優解時提前退出計算節省時間。4. 深入討論算法正確性證明與變種思考4.1 為什么貪心策略每列取眾數是最優的這是一個需要想清楚的關鍵點。對于固定len分割后的k個塊我們的目標是讓它們完全相同。考慮最終相同的那個塊它在第j列有一個確定的字符設為X_j。那么原字符串中所有在第j列位置上的字符最終都必須被修改為X_j如果原本不是X_j的話。因此對于第j列無論我們選擇哪個字符作為最終的X_j需要修改的次數都是k減去該字符在列中原本出現的次數。為了使總修改次數最小我們自然希望每一列需要修改的次數盡可能少。那么對于單獨一列顯然選擇出現次數最多的那個字符作為最終的X_j能使k - max_count最小。并且各列之間的選擇是獨立的。第j列選擇字符A作為最終字符并不會影響第j1列選擇字符B。因此分別對每一列采取貪心策略選擇眾數組合起來就是全局最優解。不存在一種方案通過讓某一列不選擇眾數來使得其他列節省更多的修改次數因為列與列之間沒有耦合關系。4.2 處理大寫字母或其他字符集題目通常說明字符串僅由小寫字母構成所以我們用了cnt[26]。如果字符集擴大比如包含大小寫字母和數字有幾種方法使用unordered_mapchar, int通用但常數時間開銷比數組大。使用更大的數組如果確認是ASCII字符可以int cnt[128] {0};然后直接用字符作為下標cnt[c]。使用vectorint(256, 0)類似數組。在競賽中如果未明確說明優先假設為小寫字母。若存疑使用unordered_map是最穩妥的除非性能成為瓶頸。4.3 如果允許的“操作”定義不同怎么辦原題是“修改任意字符”。如果操作變成“交換任意兩個字符”或者“插入/刪除字符”問題就完全不同了。交換字符這變成了一個排列問題可能需要計算字符串的循環節或者通過統計字符頻率來匹配。目標是讓字符串具有周期性且不改變字符的多重集合。插入/刪除字符這變成了編輯距離問題的一個變種或者需要動態規劃來匹配一個重復模式。復雜度會顯著上升。所以審題時明確“操作”的定義至關重要。本題的“修改”操作是最簡單的一種它只改變字符本身不改變字符串長度和字符的相對位置從而允許我們進行獨立的列統計。4.4 性能實測與復雜度再驗證為了確保我們的O(d * n)算法在n10^5時確實可行我們可以進行一個思想實驗。n的最大約數個數d(n)在10^5附近是多少一個極端例子是n83160它有超過100個約數。即使d128,128 * 100000 12,800,000也就是一千兩百萬次操作。在C中一次內層循環操作數組索引、自增、比較通常只需要幾個時鐘周期。現代CPU每秒能執行數十億次操作所以一千兩百萬次循環完全可以在幾十毫秒內完成遠低于1秒時限。在實際編碼時使用C風格數組int cnt[26] {0};比vectorint(26,0)稍快因為它在棧上分配沒有構造函數開銷。在minChangesForLength函數中對于每一列我們都重新初始化這個數組由于長度固定為26使用memset或直接循環賦零也可以但int cnt[26] {0};的寫法在循環中每次都會重新初始化是清晰且高效的。5. 常見錯誤與調試技巧即使思路正確實現時也可能踩坑。下面列舉幾個我調試時遇到過或者常見的問題5.1 下標計算錯誤這是最容易出錯的地方。計算原字符串中對應第block塊、第col列的字符位置時公式是int pos block * len col;一定要確保block從0開始到k-1結束col從0開始到len-1結束。可以寫一個簡單的測試用例驗證比如sabcdef,len2,k3。那么block0, col0 - pos0 - ‘a’block0, col1 - pos1 - ‘b’block1, col0 - pos2 - ‘c’block1, col1 - pos3 - ‘d’block2, col0 - pos4 - ‘e’block2, col1 - pos5 - ‘f’ 這符合我們將“abcdef”分成“ab”,“cd”,“ef”三個塊的直覺。5.2 忽略字符集假設如果題目沒說只有小寫字母而你用了c-‘a’作為下標遇到大寫字母或數字就會數組越界導致運行時錯誤如段錯誤。在不確定時要么先確認題意要么使用unordered_map。藍橋杯題目描述通常比較嚴謹會說明“由小寫字母組成”。5.3 未處理len n的情況在我們的算法中len必須小于n因為K要大于1。如果你在枚舉約數時不小心包含了n本身那么k n / n 1。此時對于任何一列max_count總是1因為只有1個字符k - max_count 0。這會導致計算結果為0即“不修改任何字符”但這不符合“重復字符串”的定義K1不算重復。所以必須排除len n的情況。我們的getDivisors函數通過if (i ! n)的判斷排除了它在主循環中枚舉len從1到n-1也自然排除了。5.4 初始化與重置頻率數組在minChangesForLength函數中對于每一列頻率數組必須清零。如果使用vectorint count(26, 0)它在每次循環開始時都會重新構造并初始化為0是正確的。如果使用int count[26];然后試圖用memset(count, 0, sizeof(count));來清零要確保sizeof(count)計算正確。更推薦在循環內直接定義int cnt[26] {0};寫法簡潔且不易錯。5.5 答案初始值最小修改次數的初始值應該設為一個較大的數比如n最多每個字符都改一次。不能初始化為0否則min操作永遠會得到0。5.6 測試用例設計自己設計幾個測試用例來驗證程序簡單情況s”aaaa”, 答案應為0本身已是重復字符串T”a”,K4。需要修改s”abcab”, 答案應為1如開頭所述。所有字符都不同s”abcdef”(n6)。枚舉約數1,2,3。len1: 需要把5個字符改成和第一個字符‘a’一樣不對對于len1每列只有一個字符max_count1總修改數0這里要小心len1意味著T是單個字符Kn。我們的算法k6只有1列。這一列有6個字符{a,b,c,d,e,f}出現次數最多的字符出現了1次所以修改次數6-15。這是合理的因為要變成“aaaaaa”需要改5個字符。len2: k3。列0:{a,c,e}眾數出現1次修改2次列1:{b,d,f}眾數出現1次修改2次總計4次。len3: k2。列0:{a,d}修改1次列1:{b,e}修改1次列2:{c,f}修改1次總計3次。最小值為3。所以答案是3。可以驗證比如變成“abcabc”(T”abc”, K2) 需要改3個字符d-a, e-b, f-c。邊界情況s”a”(n1)。根據題目定義長度1無法構成K1的重復字符串。我們的算法中len從1到0循環不會執行ans保持初始值n1。但也許題目期望輸出0需要仔細讀題。通常對于無法操作的情況輸出0是合理的因為無需修改就已經… 但嚴格說不滿足條件。藍橋杯真題通常保證n 2所以這個邊界可能不會出現。為了健壯性可以在開頭判斷if(n2) {cout0; return 0;}。6. 從這道題延伸的算法與字符串技巧這道“重復字符串”題雖然歸類為字符串問題但它核心考察的是枚舉、約數、貪心以及問題轉化的能力。它把字符串周期性問題轉化為了列統計問題這是一個非常漂亮的思路。與此相關的經典算法和技巧有KMP算法與字符串周期KMP算法中的next數組可以用來判斷一個字符串的最小循環節。如果一個長度為n的字符串S有長度為len的最小循環節那么n % len 0且len n - next[n]如果next[n] 0。對于本題我們可以利用這一點快速找到所有可能的周期長度嗎可以但需要注意KMP找到的是最小循環節。如果一個字符串有周期len那么len一定是最小循環節長度的倍數。所以我們可以先求出最小循環節長度min_len然后枚舉min_len的所有倍數同時是n的約數作為候選len。這可以稍微減少枚舉量但實現KMP本身也有開銷對于本題的數據范圍直接枚舉所有約數已經足夠高效。前綴和與字符統計如果題目不是修改字符而是詢問“子串中某個字符出現的次數”那么前綴和技巧就派上用場了。我們可以預處理一個二維前綴和數組pre[i][c]表示前i個字符中字符c出現的次數。這樣可以在O(1)時間內回答任何區間[l, r]內字符c的出現次數。雖然本題用不上但這是處理字符串區間統計問題的利器。哈希與字符串快速比較如果題目要求判斷兩個子串是否相等或者判斷字符串是否有周期性字符串哈希如Rabin-Karp哈希可以在O(1)時間內完成比較預處理O(n)。例如我們可以計算字符串S的哈希值然后判斷S是否等于T重復K次可以通過比較S的哈希值與T的哈希值經過特定計算后的值是否相等來判斷。這在一些更復雜的字符串周期性問題中很有用。回到這道藍橋杯真題它更像是一個思維體操訓練我們將復雜問題分解、轉化并利用基礎數據結構數組高效統計的能力。在競賽中遇到字符串問題先別急著上復雜的自動機或后綴結構想想能不能通過枚舉、貪心、前綴和等簡單方法解決。往往最優雅的解法就藏在最基礎的思考之中。