Codeforces Round #629 (Div. 3) – K-th Beautiful String

上一场CF的第一题因为没开long long上来就WA了,然后我很生气又很困就挂机了直接掉绿了……这一场我开始做正好是葡萄牙人起床了给我疯狂发邮件,我又打到一半跑了……不过这个B真的好难,我太不适合做找规律题和数学题了。

B. K-th Beautiful String

  • time limit per test: 1 second
  • memory limit per test: 256 megabytes

For the given integer $n$ $(n>2)$ let’s write down all the strings of length $n$ which contain $n−2$ letters 'a' and two letters 'b' in lexicographical (alphabetical) order.

Recall that the string $s$ of length $n$ is lexicographically less than string $t$ of length $n$, if there exists such $i$ $(1≤i≤n)$, that $s_i<t_i$, and for any $j$ $(1≤j<i)$ $s_j=t_j$. The lexicographic comparison of strings is implemented by the operator < in modern programming languages.

For example, if $n=5$ the strings are (the order does matter):

  1. aaabb
  2. aabab
  3. aabba
  4. abaab
  5. ababa
  6. abbaa
  7. baaab
  8. baaba
  9. babaa
  10. bbaaa

It is easy to show that such a list of strings will contain exactly $\frac{n⋅(n−1)}{2}$ strings.

You are given $n$ $(n>2)$ and $k$ $(1≤k≤\frac{n⋅(n−1)}{2})$. Print the $k$-th string from the list.

Input

The input contains one or more test cases.

The first line contains one integer $t$ $(1≤t≤10^4)$ — the number of test cases in the test. Then $t$ test cases follow.

Each test case is written on the the separate line containing two integers $n$ and $k$ $(3≤n≤10^5,1≤k≤min(2⋅10^9,\frac{n⋅(n−1)}{2})$.

The sum of values $n$ over all test cases in the test doesn’t exceed $10^5$.

Output

For each test case print the $k$-th string from the list of all described above strings of length $n$. Strings in the list are sorted lexicographically (alphabetically).

Example

input

7
5 1
5 2
5 8
5 10
3 1
3 2
20 100

output

aaabb
aabab
baaba
bbaaa
abb
bab
aaaaabaaaaabaaaaaaaa

题意

给出一个 $n$ 和一个 $k$ ,现在有 $n-2$ 个 a 和 $2$ 个 b ,将这 $n$ 个字母随意排列可以组成 $\frac{n⋅(n−1)}{2}$ 个字符串。按照字母顺序排列为一个有序的字符串表,输出字符串表中的第 $k$ 项。

思路

对于每一个字符串,其实可以被两个 b 分成五个部分, ... | b | ... | b | ...
样例给出的 3a2b 一共十个字符串其实已经可以找出规律。

  1. 第一个 b 之前
    显然,第一个 b 之前全部由 a 组成,十个字符串依次为:1 * 3a, 2 * 2a, 3 * 1a, 4 * 0a。所以,对于给定的 $k$ ,其实就是要求出 $1+2+\cdots+p=k+q$ 的 $p$,这个 $n-1-p$ 即为需要输出的 a 的数量。
  2. 输出第一个 b
  3. 第一个 b 与第二个 b 之间
    对于十个字符串在第一条中已经分为了四部分:1 * 3a, 2 * 2a, 3 * 1a, 4 * 0a。对于每一部分,1 * 3a中在这一条有0个 a ,2 * 2a中在这一条有1个、0个 a,3 * 1a中在这一条有2个、1个、0个 a,4 * 0a中在这一条有3个、2个、1个、0个’a’,归纳可得,输出 $q$ 个 a
  4. 输出第二个 b
  5. 输出剩余的 a
    计算可得,还需输出 $p-1-q$ 个 a

代码

#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;

const int MAXN = 1e5 + 50;
LL sum[MAXN];

int main(){
    // freopen("in.txt", "r", stdin);
    sum[0] = 0;
    for(int i=1; i<MAXN; i++) sum[i] = sum[i-1] + i;

    int T = 0; scanf("%d", &T);
    for(int rt=1; rt<=T; rt++){
        int n, k; scanf("%d %d", &n, &k);
        int p = lower_bound(sum + 1, sum + n + 1, k) - sum;
        int q = sum[p] - k;
        for(int i=1; i<=n-p-1; i++) printf("a");
        printf("b");
        for(int i=1; i<=q; i++) printf("a");
        printf("b");
        for(int i=1; i<=p-1-q; i++) printf("a");
        printf("\n");
    }
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇