[计数] aw3759. 第k个字符串(枚举+思维+aw周赛007_2)

文章目录

1. 题目来源

链接:3759. 第k个字符串

2. 题目解析

计数问题。

n 个字符,n-2a,2 个 b,将 n 个中的两个字符变成 b,总的不同方案就是 C n 2 C_n^2 Cn2​ 没有问题。

很显然,是有规律的计数问题。按照字典序枚举即可,先枚举第一个 b 所在位置,再枚举第二个 b 的所有情况,b 在倒数第一个位置,则另一个 b 有一种情况,b 在倒数第二个位置,则另一个 b 有两种情况…

跳过前面的所有字典序,确定第一个 b 的位置,剩余了 k 个序列,第二个 b 就在第 k 个位置即可。

自己动手推推规律就行了。


时间复杂度: O ( l o g n ) O(logn) O(logn)

空间复杂度: O ( 1 ) O(1) O(1)


标程,直接拿数组做就行了,从 na 中修改两个 b 就行了。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        int n, k;
        cin >> n >> k;
        for (int i = n - 1; i; i -- )
        {
            if (k > n - i) k -= n - i;
            else
            {
                string s(n, 'a');
                s[i - 1] = s[n - k] = 'b';
                cout << s << endl;
                break;
            }
        }
    }

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int n, k;

int main() {
    int T; cin >> T; while (T -- ) {
        cin >> n >> k;
        int t = 0, cnt = 0;
        while (k > t) cnt ++ , k -= t, t ++ ;       // cnt 为第一个 b 的位置
        string res(n - 2, 'a');
        res.insert(n - cnt - 1, 1, 'b');
        res.insert(n - k, 1, 'b');                  // 剩余的 k 即为第二个 b 的位置
        cout << res << endl;
    }

    return 0;
}
上一篇:clickhourse-007之click-backup工具介绍


下一篇:PYTHON 100days学习笔记007-3:字符串和常用数据结构