LHPC 2016 pE. 教官的名字 ( Ad hoc, 構造, String, square-free sequence )

這題是需要想一下的構造題。本來想放棄亂寫 hash 臨時判斷，本地建答案，但突然想遞迴構造看看。
一開始我們有正確的 "ABC"
如果把 A, B, 和 C 當成各自不同的 pattern, 也就是說令 A = 某個 'A', 'B', 'C' 組成的亂七八糟的字串，B, C 亦同，並保證一些性質，似乎可以遞迴構造我們要的答案。考慮 "ABCACB"，A = "ABC" ( 不能 "ABCA" ), B = "AC", C = "B" ( 不能 "CB", 看看 A )，我們可以保證 A, B, C 三個 pattern 怎麼接都不會有連續重複的 pattern。雖然還是不夠嚴謹，但丟丟看就 AC惹 =v=。
p.s. 事後知道這叫 square-free sequence, square 指連續重複出現兩次

void solve(){
    int N; cin >> N;
    string s = "ABC";
    while( s.size() < (int) 1e5 ){
        string ns;
        for( int i = 0; i < s.size(); ++i ){
            if( s[ i ] == 'A' )
                ns += "ABC";
            if( s[ i ] == 'B' )
                ns += "AC";
            if( s[ i ] == 'C' )
                ns += "B";
        }
        swap( s, ns );
    }
    cout << s.substr( 0, ( int ) 1e5 ) << endl;
}