Codeforces 1493C - K-beautiful Strings (設計解題、實作題)

題目大意

將給你一個字串 s，以及 k，請你找出一個字串比 s 下一個小的字串並且裡面的同個字母數量都能 mod k == 0 還有產生的字串長度必須等於 s

題目連結

重點觀念

• 抓到題目重點
• 想到一個好寫的程式碼流程

分析

對不起，我覺得我的重點觀念很像在講幹話…，但設計解題就是這樣嘛RRRR。
相信大家都能夠推出重點來，只是大家不知道要怎麼寫這題目，有抓到重點但是寫不出來的那種感覺。

以下是我進行整理的點，由�我在大大中領會出來的。

• \(題目字串長度 \% k = 0 \)，如果不成立就可以輸出 -1
  因為如果不等於的話，勢必會有一個英文字母沒有辦法 mod k
• 再來我們判斷需不需要修改字串中的字元，如果不用就直接輸出原本的字串
  這點很重要，如果我們有先處理這步驟，那後面的程式會好寫很多，我就是沒想到這步才卡住
• 需要修改時，那我們就要進行以下處理
  • 從題目的字串尾巴開始判斷是否要修改字元
    由於題目只能找比 s 下一個小的字串，因此我們先修改字串尾巴的字元，能夠更快找到比 s 下一個小的字串
  • 如果在某 index 下修改字元，判斷要填塞哪個字母才能符合同個字母數量都能 mod k == 0
    這時，我們要計算出在某 index前面的字串們，還要再塞入一個字元幾次，例如 ‘a’ 個字元兩次才能符合同個字母數量都能 mod k == 0
  • 推敲出公式 (k- 現在某個字元在某 index 前面字串裡的數量 %k)%k 此公式為還要在幾個相同字元的數量才能符合同個字母數量都能 mod k == 0
    假如一個字串 aabb，k = 3，那我們勢必要在給各一個 a, b 才能符合同個字母數量都能 mod k == 0此條件，可能會有人不太懂為甚麼前面要 (k - and %k，是為了假如現在某個字元在某 index 前面字串裡的數量 = 0時，才不會出現需要 k 個字元的情況發生。

現在我們獲得這些重點後，我們就可以來寫程式了！一些重點與小技巧在程式碼那邊進行說明。

參考連結

• Codeforces Round #705 (Div. 2) 1493题解A. Anti-knapsack/B. Planet Lapituletti/C. K-beautiful Strings - by �我在

心得

RRRRR，其實我應該寫得出這題的，只是我抓出了這些重點後還是沒有寫程式的想法，透過 �我在大大的程式碼後，我才發現有一個 sum(題目程式碼的陣列，用於記錄在每個字串前綴長度時，每個字母的數量值) 是多麼重要的一件事情！我那時要是有想到他，我就會解出來了！

總之希望自己在學演算法是有意義的，我覺得我正在變聰明，我也從演算法中獲取了很多知識，似乎每天努力的學習就是寫演算法的義務吧！

嘛，我也不知道為甚麼我會走到這條路，總之我繼續加油吧！

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 100020
using namespace std;
int T, k, n;
int cnt[30], sum[MAXN][30], now;
//cnt 如果在這 index 後的字串後綴都替換後，需要給予的字元數量，index 是 a,b,c 這種感覺
//sum[字串當前長度][字母 (a,b, c)] = 數量，也就是字串當前長度的某個字元的數量
string s; //輸入題目資料用
 
int check(int x){ //判斷在此 index 下能否表達出題目所要的答案字元
    for(int i = s[x]-'a'+1; i < 26; i++){ //從修改的 index 字元的下一個開始，到 z 結束
        memset(cnt, 0, sizeof(cnt)); //將 cnt 歸為零，cnt 每次都要 clear
        //cnt 用來表示，我們的 cnt[字母 (a,b,c)] = 數量，也就是每個字母需要幾個數量才能符合，
        //同個字母數量都能 mod k == 0

        int remain = n-x-1; //如果從此 index 開始修改，那後面的字元我們可以任意變動
        //但也只有這個數量可以變動，注意要 -1，因為 x 這個 index 的字元是固定的，
        //必須要是 i，才有符合當前字源比 s[i] 小

        for(int j = 0; j < 26; j++){ //每個字元還需要多少字元才能符合，
        //同個字母數量都能 mod k == 0
            now = sum[x][j]; //當前長度的 j + 'a' 字元有多少數量
            if(j == s[x]-'a') now--; //由於我們是紀錄當前長度，但是我們要替換現在此 index，
            //因此要將 now-1，因為 s[i] 這個字元我們不會使用，如果使用就不是修改此 index
            else if(i == j) now++; //因為在這邊我們會用 i+'a' 此字元，所以將 now +1，
            //表示之後可以少一個 i+'a' 字元，來補我們這邊用過的

            remain -= (k-now%k)%k; //減掉我們可以用的長度字元
            cnt[j] += (k-now%k)%k; //此字元至少需要多少長度才符合 同個字母數量都能 mod k == 0
            if(remain < 0) break; //如果 < 0，表示要比題目原本字串的長度更長才能符合，因此退出
        }
        if(remain < 0) continue; //判斷下一個字元替換此 s[i]

        //如果還有剩下的長度可以被使用，那我們就全加給 'a' 就好，不需要擔心 a 字母會不會 % k != 0，
        //因為剩下的長度必定會 %k == 0，否則我們整理的第一點就不會符合。
        //證明: 每個字母的長度必須都 %k == 0，因此如果有剩下的長度 > 1，就表示題目的長度 %k != 0
        cnt[0] += remain;
        return i; //表示此 i+'a' 此字串替換給 s[i] 是好選擇，所以回傳
    }
    return 0;
}

string solve(){
    if(s.length() % k != 0) return "-1"; //我們整理的第一個重點

    for(int i = 0; i < 26; i++) sum[0][i] = 0; //歸零，不要用 memset，我這樣更省時間
    for(int i = 0; i < n; i++){ //開始計算在每個長度時，每個字元的數量
        sum[i][s[i] - 'a'] += 1;
        for(int j = 0; j < 26; j++) sum[i+1][j] = sum[i][j]; //狀態更新給下一個長度
    }

    int flag = 1; //判斷是否不需要修改
    for(int i = 0; i < 26; i++){
        if(sum[n-1][i] % k != 0){ //需要修改
            flag = 0; 
            break; //退出
        }
    }
    if(flag == 1) return s; //如果是 1 表示不需要修改，就是我們整理的第二個重點

    string ans = ""; //答案
    for(int i = n-1; i >= 0; i--){ //從字串最尾巴開始進行修改
        flag = check(i); //判斷這邊修改為哪個字元更好，0 表示都不好
        if(flag){ //如果 > 0，表示有可以修改的字元
            ans = s.substr(0, i) + (char) (flag+'a'); 
            //原本的字串長度從 0 到 i-1 加上修改的字元，
            //注意 C++ 的 substr(position, len) 函式與其他語言語法不同

            //透過字典序依序將每個字母需要的數量補入 string，這裡的 string(次數, 字元)
            for(int i = 0; i < 26; i++) ans += string(cnt[i], i+'a');
            return ans; //回傳答案
        }
    }
    return ans;
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> T;
    while(T--){ //輸入題目資料
        cin >> n >> k >> s;
        cout << solve() << '\n'; //給 sovle 回傳答案
    }
    return 0;
}

思考流程

透過紙筆與黑板而思考而成的片段，放在網路上供我紀念XD

錯誤的程式碼就不放上來讓大家見笑了QQQQ。