题解：P6495 [COCI2016-2017#2] Tavan

· · 题解

题意

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

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

现在要将所有的替换情况列举出来，然后将这些情况按字典序来排序，排序之后输出字典序第 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 的代码就不给了，完结撒花！！！