EOJ Monthly 2019.11 A

EOJ Monthly 2019.11 A(进制转换)

“欢迎您乘坐东方航空公司航班 MU5692 由银川前往上海......”

“我们的飞机很快就要起飞了，请收起小桌板，摘下耳机......”

收起了小桌板，摘下了耳机，Cuber QQ 突然无所事事了。

放耳机进书包的时候，Cuber QQ 无意带出了一些小纸条。

是以前的回忆。

纸条在书包中已经存在了不知道多久。

水渍泛黄了纸张，有些字他不能认出来。

具体来说，信件是一个包含 N 个字母的单词。

其中有 M 个难以辨认的字母，用字符 # 代替。

Cuber QQ 用残存的回忆给对每个难以辨认的字母都给出了 K 个不同的候选字母。

为了方便比较哪个更接近于自己的回忆，Cuber QQ 在纸上列出了所有可能的单词。

在看过这些单词以后，Cuber QQ 认为按照字典序排名，第 X 个单词就是原来的单词。

你能知道 Cuber QQ 以前写了什么吗？

输入格式

第一行整数 N,M,K 和 X (1≤N≤500000,1≤M≤N,1≤K≤26,1≤X≤1018) 。

第二行长度为 N 的单词，包含小写字母和 # 。

接下来 M 行，每行包括 K 个字母，表示第 i 个难以辨认的字母可能由这些字母代替。

保证 X 不超过能构造的单词数量。

输出格式

一行一个字符串，表示答案。

样例

input

5 2 3 4

c##nb

std

lws

output

cslnb

原问题可以转换成\(k-1\)的进制转换问题

题意：#是不确定的字母，下面每一行给出候选字母，按照字典序组合后选择第\(x\)个组合就是答案。

字典序，先排序，总共有\(k^m\)种可能，由于每一行的候选个数都相等，所以就是一个进制转换问题了。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstring>

using namespace std;

typedef long long ll;

const int maxn = 500000 + 5;

ll a[maxn];

char s[maxn];

char stemp[maxn];

char res[maxn];

ll len;

int main()

{

    ll n,m,k,x;

    scanf("%lld%lld%lld%lld",&n,&m,&k,&x);

    x--;

    scanf("%s",s);

    int cnt=0;

    while(x)

    {

        a[cnt++]=x%k; x/=k;

    }

    cnt=0;

    for (int i = 0; i < m; i++)

    {

        scanf("%s", stemp);

        sort(stemp, stemp + k);

        res[cnt++]=stemp[a[m-i-1]];

    }

    cnt=0;

    for (int i = 0; i < n; i++)

    {

        if (s[i] == '#')

        {

            printf("%c",res[cnt++]);

        }

        else printf("%c",s[i]);

    }

    return 0;

}