【Week15实验 D】瑞瑞爱上字符串【模拟】
程序员文章站
2024-03-17 21:48:16
...
题意:
瑞瑞最近迷上了字符串,因此决定出一个字符串的题。
给定两个正整数 N、K,考虑所有由 N - 2 个 a 和 2 个 b 组成的字符串,要求输出其中字典序第 K 小的。
例如当 N = 5 时,共有如下 10 种组成方式:
aaabb、aabab、aabba、abaab、ababa、abbaa、baaab、baaba、babaa、bbaaa。
多组数据,第一行给定 T,表示数据组数。(1 ≤ T ≤ 1e4)
对于每组数据,给出两个正整数 N、K。(3 ≤ N ≤ 1e5, 1 ≤ K ≤ min(2e9, N * (N-1) / 2 ))
N 的总和不会超过 1e5。
对于每组数据,输出长度为 N 的字典序第 K 小的字符串。
思路:
可以将所有字符设为a,然后寻找b的位置。默认b在字符串倒数第二个和倒数第一个。
根据上图可以找到两个b前进的格数,倒数第二个b要前进y-1格,倒数第一个b要前进k-z格。
总结:
一道求公式的模拟题。
代码:
#include <iostream>
#include <cmath>
using namespace std;
long long int n,k;
char c[100010];
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n>>k;
for(int i=0;i<n;i++)
c[i]='a';
c[n]='\0';
long long int sq=1+8*k; //k最大2e9,会爆int
double x=(sqrt(sq)-1)/2;
long long int y=ceil(x);
//倒数第二个b要往前y-1格
long long int index1=n-2-(y-1);
c[index1]='b';
long long int z=(1+y-1)*(y-1)/2+1;
//倒数第一个b要往前k-z格
long long int index2=n-1-(k-z);
c[index2]='b';
cout<<c<<endl;
}
}
上一篇: 背包问题3(多重背包)