本文主要是介绍【Week15实验 D】瑞瑞爱上字符串【模拟】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
瑞瑞最近迷上了字符串，因此决定出一个字符串的题。
给定两个正整数 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; }
}
这篇关于【Week15实验 D】瑞瑞爱上字符串【模拟】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
