codeforces 1328 B. K-th Beautiful String

题意：

就是找到第 k k k 个全排列的字符串

通过找规律，第一个 b b b 在倒数第二位有 1 1 1 个，倒数第三位 2 2 2 个，倒数第四位三个，第二个 b b b 的位置就是 k − 1 − 2 − 3 − . . . k-1-2-3-... k−1−2−3−... 剩下的数字倒着数。这样位置就能确定了。然后倒着输出即可。

AC代码;

const int N = 100010;
int n, m, k;
int res, tmp, cnt;
ll sum[N];
char ans[N];
int pos, p1, p2;
void init()
{
	sum[0] = 0;
	rep(i, 1, N - 1)
		sum[i] = i + sum[i - 1];
}

int main()
{
	int t;
	sd(t);
	init();
	while (t--)
	{
		sdd(n, k);
		p1 = 1, p2 = 0;
		pos = lower_bound(sum + 1, sum + N, k) - sum;
		p1 += pos;
		if (sum[pos] >= k)
			pos--;
		k -= sum[pos];
		p2 += k;
		rep(i, 1, p2 - 1)
			ans[i] = 'a';
		ans[p2] = 'b';
		rep(i, p2 + 1, p1)
			ans[i] = 'a';
		ans[p1] = 'b';
		rep(i, p1 + 1, n)
			ans[i] = 'a';
		per(i, n, 1)
			printf("%c", ans[i]);
		puts("");
	}
	return 0;
}