思路
-
观察发现左边的b的移动是呈等差数列的
-
其位置为-2 -3 -3 -4 -4 -4 -5 -5 -5 -5 ... ,那么右边的b的最左位置是左边b的位置+1
也就是说,给定K的值,只需要判断k是在哪一组就能确定左边的b的位置了,假设是第m组,那么左边b的位置就是n - m
接着就是确定右边b的位置,而它的位置只需要判断它是在这一组的第几个数就够了,假设是第q个数,那么右边b的位置就是n - q + 1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
char str[N];
int main(){
int t;
cin >> t;
while(t --){
int n, k;
cin >> n >> k;
ll ans = 0;
for(ll i = 1; i <= n; i ++){
if((i * i + i) / 2 >= k && ((i - 1) * (i - 1) + (i - 1)) / 2 < k){
ans = i;
break;
}
}
ll right = k - ((ans - 1) * (ans - 1) + (ans - 1)) / 2;
for(int i = 1; i <= n; i ++)
str[i] = 'a';
str[n - ans] = 'b';
str[n - right + 1] = 'b';
for(int i = 1; i <= n; i ++)
cout << str[i];
cout << endl;
}
return 0;
}
/* //本来还想用二分做,但写起来太麻烦,出错了,就直接O(N)了
int l = 1, r = 100010;
int mid = 0;
while(l < r){
mid = l + r + 1 >> 1;
if((mid * mid + mid) / 2 >= k && (((mid - 1) * (mid - 1) + (mid - 1))) / 2 < k)
break;
else if((mid * mid + mid) / 2 < k)
l = mid;
else if((mid * mid + mid) / 2 >= k && (((mid - 1) * (mid - 1) + (mid - 1))) / 2 >= k)
r = mid - 1;
}
for(int i = 1; i <= n; i ++)
str[i] = 'a';
str[n - mid + 1] = 'b';
int t = k - ((mid - 1) * (mid - 1) + (mid - 1)) / 2;
str[n - t + 1] = 'b';
for(int i = 1; i <= n; i ++)
cout << str[i];
cout << endl;
*/