B. K-th Beautiful String

Link

Solution

披着字符串外壳的数学题，观察可发现关键在于确定两个b的位置，我的方法和标答略有不同但原理是一样的，我说我的方法：

首先做一个n层金字塔：

1

23

456

78910

……

可以发现已知n、k，两个b的位置和k所在金字塔层数有关，一开始先打个表，二分找出所在层，推导公式搞一搞就出来了，虽然空间消耗大但貌似速度比标答还能快点。

Code

LL a[maxn];

int main(int argc, char **argv) {
    int t;
    cin >> t;
    for (LL i = 1; i <= 1e5; i++)a[i] = (i * (i + 1)) / 2;
    while (t--) {
        int n, k;
        cin >> n >> k;
        int pos = lower_bound(a + 1, a + 1 + n, k) - a;
        int pos1b = n - pos - 1, pos2b = n - pos + a[pos] - k;
        for (int i = 0; i < n; i++)
            if (i == pos1b || i == pos2b)cout << 'b';
            else cout << 'a';
        cout << endl;
    }
    return 0;
}