[codeforces 1328B] K-th Beautiful String 研究倒数第二个字母b的位置

Codeforces Round #629 (Div. 3)   比赛人数10967

[codeforces 1328B]  K-th Beautiful String    研究倒数第二个字母b的位置

总目录详见https://blog.csdn.net/mrcrack/article/details/103564004

也在线测评地址https://codeforces.ml/contest/1328/problem/B

一开始，还一度以为做不出该题，研究了该题C(n,2)的由来，

有n个空位，任选2个，放入b的情况有C(n,2)种，剩下的位置放入a

研究倒数第二个字母b的位置

手工模拟如下

研究倒数第2个b所处不同位置对应的形态
    aaabb   1    １种形态

    aabab   1
    aabba   2    2种形态

    abaab   1
    ababa   2
    abbaa   3    3种形态

    baaab   1
    baaba   2
    babaa   3
    bbaaa   4    4种形态

可以看到 第2个b所处不同位置对应的形态
确定了了 第2个b所处位置后，第1个b所处位置，也就容易确定了。

递增规律也就找到了。

 AC代码如下

#include <stdio.h>
#define maxn 100010
#define LL long long
LL cnt[maxn],sum[maxn];//cnt[i]记录倒数第2个b,所处字串倒数第i位时，对应的形态数量
char s[maxn];
int main(){
	int i,t,n,k,j;
	for(i=2;i<=100000;i++)cnt[i]=cnt[i-1]+1,sum[i]=sum[i-1]+cnt[i];//sum[i]记录cnt[i]的前缀和
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&k);
		for(i=2;i<=n;i++)
			if(k<=sum[i])break;
		j=i,k-=sum[j-1];
		for(i=1;i<=n;i++)s[i]='a';//字串先用a填充
		s[n+1]='\0';//字串结尾标记。
		s[n-j+1]='b';//记录倒数第2个b所处字串位置
		s[n-k+1]='b';//记录倒数第1个b所处字串位置
		printf("%s\n",s+1);
	}
	return 0;
}