CF1328B K-th Beautiful String

题意：给一个长度n的ab字符串，要求包含（n-2）个a和2个b，进行字典序排列，求第k个字符串

思路：由于只有2个b点，因此可以枚举b的位置来得到第k个排列。我们假设第一个b点位置为l，第二个为r，很明显，l的范围是1~n-1,r的范围是l+1~n。

但是如果逐个枚举k次，k<=2e9一定会TLE。因此我们先从后往前枚举l,对于每一个l所对应的r的个数（n-i）累加到计数器sum中。如果sum>=k了，说明排列已经超过了k个，答案一定在当前l中，l确定了，r也就可以很容易推出来了

code:

#include
using namespace std;
#define ll long long
#define PII pair
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define fo(i,a,b) for(int i=a;i>=b;i--)
//#pragma GCC optimize(2)
/*inline int read() {
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    } while('0' <= ch && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    } return x * f;
}*/
int t,n,k;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);//输入
        int sum=0,l,r;//sum是计数器
        fo(i,n-1,1){//从后往前枚举l
            sum+=n-i;//n-i是每个l对应的r的数量
            if(sum>=k) {//如果超过k，注意相等要取，因为相等时l也是当前i
                sum-=n-i;//t退回到上一状态
                l=i;//确定l
                r=n-(k-sum)+1;//推出r
                break;//退出循环
            }
        }
        fr(i,1,n){//输出
            if(i==l||i==r) printf("b");
            else printf("a");
        }
        cout<<endl;
    }
    return 0;
}