正经题解｜增长的字母

题目分析

所有大写字母中只有 A 不会发生变化，B 是除 A 之外增长最慢的，B 在第 $K$ 天的个数为 $2 ^ {K - 1}$。而题目中 $K$ 固定为 $10^6$，而 $N$ 必定小于 $2 ^ {K - 1}$。
如果截止到 $S_N$ 全是 A 答案则为 A，否则答案为第一个不为 A 的字母。

AC代码

#include <iostream>
using namespace std;
typedef long long ll;
int main() {
    ll k;
    string s;
    cin >> s;
    cin >> k;
    int idx = 0;
    ll cnt = 0;
    for(int i=0;i<s.size();i++) {
        if (s[i] == 'A') {
            cnt++;
        }else {
            idx = i;
            break;
        }
    }
    if (k <= cnt) {
        cout << 'A';
    }else {
        cout << s[idx];
    }
    return 0;
}

复杂度分析

$O(|S|)$