Codeforces 110B Lucky String 字典序最小幸運字符串構造

Codeforces 110B Lucky String 題目解析

構造長度 n (≤10⁵) 的字典序最小字符串，使每個字母出現位置的相鄰差值為幸運數字 (僅含 4 和 7 的數字，如 4, 7, 44, 47...)。

關鍵觀察

相鄰差值為 4 或 7。最小幸運數是 4。若每個字母每隔 4 位出現一次，差值恆為 4。使用 4 個字母循環：a b c d a b c d... 滿足條件且字典序最小。

構造規律

位置:  1  2  3  4  5  6  7  8  9 ...
字符:  a  b  c  d  a  b  c  d  a ...
差值:     4  4  4  4  4  4  4  4 ...

第 i 位 (1-based)：(i-1)%4 → 'a'+余數，余數 3 時為 'd'。

C++ 代碼實現

#include <iostream>
using namespace std;

char s[1000000];

int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++) {
            if ((i + 1) % 4 != 0)
                s[i] = 'a' + (i + 1) % 4 - 1;
            else
                s[i] = 'd';
        }
        s[n] = '\0';
        puts(s);
    }
    return 0;
}

正確性證明

• 字典序最小：優先用 'a'，盡早重複 'a' (間隔 4)
• 差值為 4：每字母週期 4，相鄰出現位置差 4
• 4 是最小幸運數，無法用更小間隔
• 4 個字母足夠，更多字母只會增大字典序

樣例驗證

n=5 → abcda (a 在 1,5 差 4)
n=3 → abc (無重複字母，自動滿足)