K-th Beautiful String

2023-12-29 21:51:23

K-th Beautiful String

题面翻译

给定正整数 n , k n,k n,k,考虑所有由 n ? 2 n-2 n?2a 2 2 2b 构成的字符串,输出其中字典序第 k k k 小的。

多组数据, T ≤ 1 0 4 T\le10^4 T104 3 ≤ n ≤ 1 0 5 3\le n\le 10^5 3n105 k ≤ min ? ( 2 × 1 0 9 , n × ( n ? 1 ) 2 ) k\le\min(2\times10^9,\frac{n\times(n-1)}2) kmin(2×109,2n×(n?1)?) ∑ n ≤ 1 0 5 \sum n\le10^5 n105

题目描述

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 \le i \le n $ ), that $ s_i < t_i $ , and for any $ j $ ( $ 1 \le 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 \cdot (n-1)}{2} $ strings.

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

输入格式

The input contains one or more test cases.

The first line contains one integer $ t $ ( $ 1 \le t \le 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 \le n \le 10^5, 1 \le k \le \min(2\cdot10^9, \frac{n \cdot (n-1)}{2}) $ .

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

输出格式

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).

样例 #1

样例输入 #1

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

样例输出 #1

aaabb
aabab
baaba
bbaaa
abb
bab
aaaaabaaaaabaaaaaaaa

int findfirst(int n,int *second)
{
	int i = 1;
	int sum = 0;
	for (;;)
	{
		for (int m=1;m<=i;m++ )
		{
			sum++;
			if (sum == n)
			{
				*second = m;
				return i + 1;
			}
		}
		i++;
	}
}
//时间超限的程序。下面没有用
#include<stdio.h>
int main(void)
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		
		int n = 0, k = 0;
		char arr[1000000] = { 0 };
		scanf("%d %d", &n, &k);
		int first = 1;//第1个b位置
		int s = 0;
		int j = 1;
		while (s < k) {
			s += j;
			j++;
		}
		first = j;
		int second = first - 1 - (s - k);
		for (int i = 1; i <= n - first; i++)
		{
			printf("a");
		}
		printf("b");
		for (int i = 1; i <= first - second-1; i++)
		{
			printf("a");
		}
		printf("b");
		for (int i = 1; i <= second - 1; i++)
		{
			printf("a");
		}
		printf("\n");

	}
	return 0;
}

不会二分硬是做成数学题。。。。

文章来源:https://blog.csdn.net/2301_80096362/article/details/135298299
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。