CF1328B K-th Beautiful String

CF1328B K-th Beautiful String，然而CF今天却上不去了，这是洛谷的链接

题意

一个长度为\(n\)的字符串，有2个\(\texttt{b}\)和\(n-2\)个\(\texttt{a}\)

按字典序排序后，问你第\(k\)个是啥

\(n\leq 10^5\)

由于我们相信CF从来不卡常，所以这实际是个\(O(n)\)找规律

看题目里的例子：

aaabb

aabab

aabba

abaab

ababa

abbaa

baaab

baaba

babaa

bbaaa

可以发现，如果只看前面一个\(\texttt{b}\)的运动轨迹，是从后向前以为一位移动的

而对于靠后的一个\(\texttt{b}\)，当前面那个\(\texttt{b}\)确定后，它也是从最后一位向前移动，直到移动到前面那个\(\texttt{b}\)的后一位

然后，它又回到最后，前面那个\(\texttt{b}\)再往前走一位

所以我们可以从后到前枚举第一个\(\texttt{b}\)的位置，假设当前位置是\(i\)，那么这一种情况就有\(n-i\)个字符串

讨论如下：

\(k>n-i\)，那么，\(k\rightarrow k-(n-i)\)，就是说这\(n-i\)个字符串里面没有要找的，再向前考虑
其余情况，也就是我们要找的第\(k\)个字符串就在这\(n-i\)个，那么第二个\(\texttt{b}\)就是在第\(n-k+1\)为，输出就行

可以结合上面的例子理解

放上代码

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<iomanip>

#include<cstring>

#define reg register

#define EN std::puts("")

#define LL long long

inline LL read(){

	LL x=0,y=1;

	char c=std::getchar();

	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}

	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}

	return y?x:-x;

}

LL n,k;

int main(){int T=read();while(T--){

	n=read();k=read();

	for(reg int i=n-1;i;i--){

		if(k>n-i) k-=n-i;

		else{

			for(reg int j=1;j<i;j++) std::putchar('a');

			std::putchar('b');

			for(reg int j=i+1;j<n-k+1;j++) std::putchar('a');

			std::putchar('b');

			for(reg int j=n-k+2;j<=n;j++) std::putchar('a');

			break;

		}

	}

	EN;

}

	return 0;

}

巴特西

CF1328B K-th Beautiful String

题意

最新文章

热门文章