蒟蒻的小窝

蒟蒻的小窝

题解 P6495 【[COCI2016-2017#2] Tavan】

posted on 2020-08-27 19:25:52 | under 题解 |

一拿到题,笨蛋的方法就是用 $dfs$ 枚举排列数呗,但仔细一想,根本没必要这么麻烦,答案是要找出将每个单词中每个字母按照字典序从小到大排序后的第 $x$ 个,其中每个单词总共有 $k$ 个字母,那么我们只需要把它理解为 $k$ 进制数不就得了?

Code:

#include<bits/stdc++.h>
using namespace std;
const int MAXN=510;
int n,m,k,x,br,pos[MAXN];
char s[MAXN],a[MAXN][30];
int main(){
    scanf("%d%d%d%d",&n,&m,&k,&x);
    scanf("%s",s);
    for (int i=0;i<n;i++)
      if (s[i]=='#') pos[br++]=i;
    for (int i=0;i<m;i++) scanf("%s",a[i]);
    x--;
    for (int i=0;i<m;i++) sort(a[i],a[i]+k);//将每个单词中的字母按照字典序排序
    for (int i=0;i<m;i++) s[pos[i]]=a[i][0];//这里在赋初值,为什么呢?因为怕x=0,这样下面直接break掉了,答案就是空的。
    for (int i=m-1;i>=0;i--){
        if (!x) break;
        s[pos[i]]=a[i][x%k];//转化
        x/=k;//转化完成之后干掉1位
    }
    s[n]=0;
    printf("%s\n",s);
    return 0;
}