【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; 
	}
}