自动搬运

查看原文

来自洛谷，原作者为

	FZY_CZY 对于人生而言，重要的不是凯旋，而是奋斗

搬运于2025-08-24 22:21:20，当前版本为作者最后更新于2025-01-14 19:02:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

感觉这道题的题意可能一开始有一点晦涩难懂（反正我是这样的）。

题目。我来按我的理解来解释一下这道题。首先我们有一个字符串，但是这个字符串中包括了一些字符 #，这些 # 字符按照次序对应下面的字符串，而这个字符串里面的所有字符就是这个 # 号字符可以替换的备选。

现在要将所有的替换情况列举出来，然后将这些情况按字典序来排序，排序之后输出字典序第 $x$ 个字符串（如果有什么不明白的点可以私信或者在评论区问，一般来说一天内会有回复）。

思路

思路 1

其实，当我们对于题意的理解足够的时候，这道题的思路就会很自然的浮出水面。

我们考虑到字典序，所以我们可以先把字符串（第 $3$ 行到第 $3+m$ 行）进行一个排序，然后组合，组合后找到第 $x$ 位。

思路 2

我再提供另一种思路，那就是转换思想（应该是这样的）。

我们可以把我们这些不同的组合状态转化成一个 $k$ 进制数，然后直接拆分 $x$，把拆分过后的结果填入原本的字符串即可。

我在处理字符串的时候有一个小习惯，喜欢的可以学习一下，就是 s=" "+s;，这样我们在处理字符串 s 的时候下标可以从 $1$ 开始，符合一部分人的习惯。

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m,k,x,c[N],cur;
string s,a[N];
int main(){
	cin>>n>>m>>k>>x;
	cin>>s;
	s=" "+s;
	for (int i=1;i<=m;i++)
	{
		cin>>a[i];
		sort(a[i].begin(),a[i].end());
	}
	x--;
	while (x)
	{
		c[++cur]=x%k;
		x/=k;
	}
	for (int i=n,j=m,k=1;i>=1;i--)
		if(s[i]=='#') s[i]=a[j--][c[k++]];
	for (int i=1;i<=n;i++) cout<<s[i];
	return 0;
}

思路 1 的代码就不给了，完结撒花！！！