专栏文章

CF1620C

DDDF_
CF1620C题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio0lmsm
此快照首次捕获于
2025/12/02 11:24
3 个月前
此快照最后确认于
2025/12/02 11:24
3 个月前
查看原文

题面

有一个长为 nn 串由 a 和 * 组成，里面所有的 * 都可以替换为 ii 个 b（0≤i≤k0 \le i \le k）。求将所有 * 替换后，按字典序排序第 xx 小的串。

题解

由于不管填法只管可以得到的所有串，所以可以将连续多个 * 合并为一个空格，这个空格就可以填 t×kt \times k 个 b（tt 为 * 个数）。
手玩一下，填最右边肯定增加的排名最少，填满最右边的空格后，上一位填一个并把这一空格清空，排名就 +1+1，可以在最右边继续填。
这是进位。
于是可以把这个串转化成一个随机进制数，每一位的进制不同，然后题目转化为求从 00 开始第 xx 小的数。
然后求出这个数，对于每一个空格，它在数中这一位是多少，就在这个空格中填多少个 b。
怎么求这个数？先令 x=x−1x=x-1，然后对 xx 进制转换为这个数即可。
记得要防爆 long。如果这一位比 xx 大，就直接设为 x+1x+1。

代码

CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int _;
int n,tot;
ll k,x;
ll num[2025];
int put[2025];
char s[2025];
void solve() {
	tot=0;
	scanf("%d%lld%lld",&n,&k,&x),x--;
	cin>>(s+1);
	if(k==0) {
		for(int i=1;i<=n;i++) if(s[i]=='a') putchar(s[i]);
		puts("");
		return;
	}
	for(int i=1;i<=n;i++) {
		if(s[i]=='*') {
			int j=i;
			num[++tot]=1;
			while(s[j]=='*'&&j<=n) num[tot]+=k,j++;
			i=j;
		}
	}
	num[++tot]=1;
	for(int i=tot-1;i;i--) {
		if(num[i]>x/num[i+1]&&num[i+1]>x/num[i]) num[i]=x+1ll;
		else num[i]*=num[i+1];	
	}
	for(int i=1;i<=tot;i++) put[i]=max(x/num[i],0ll),x%=num[i];
	int l=1;
	for(int i=1;i<=n;i++) {
		if(s[i]=='*') {
			int j=i;
			while(s[j]=='*') j++;
			l++,i=j-1;
			while(put[l]) putchar('b'),put[l]--;
		}
		else putchar('a');
	}
	puts("");
	return;
}
int main() {
	scanf("%d",&_);
	while(_--) solve();
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...