https://acm.ecnu.edu.cn/ 华东师范大学在线评测网站
今天这个题目来自华东师范大学的校赛，比icpc稍难一些，在2019年11月29日周五19：30开始，持续2.5个小时
以下是题干
A. 纸条
单点时限: 2.0 sec，内存限制: 256 MB
“欢迎您乘坐东方航空公司航班 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 不超过能构造的单词数量。
输出格式
一行一个字符串，表示答案。
样例输入
5 2 3 4
c##nb
std
lws
样例输出
cslnb
Solution
看到这道题首先模拟一下样例，就大概知道该怎么做了
求这样M个空位，每个空位有K种可能的，希望得出按字典序排列的第X种，相当于求X用K的次幂表示。这就把这道题目抽象成了一个数学问题
(X=a_M*K^M+a_{M-1}*K^{M-1}+...+a_{2}*K^2+a_{1}*K+a_0)
用递归解决就可以了
要注意的点是小心预处理，前面一部分填1，也就是在每个空位内选第一个可能字符，后面一部分填M
/*
* Created by AronQi
* For personal training
* 2019/09/28
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define RG register
using namespace std;
template<class Type> inline void R(Type &x)
{
RG int c=getchar();
for(;c<48||c>57;c=getchar());
for(x=0;c>47&&c<58;x=(Type)10*x+c-48,c=getchar());
}
int N,M,K,Tag[5000001];
char Buf[5000011],Su[27];
bool Ap[27];
unsigned long long Po[5000001],X;
void Dg(int i,unsigned long long rst)
{
Tag[M-i+1]=rst/Po[i-1];
if(rst%Po[i-1]!=0LL)
{
Tag[M-i+1]++;
Dg(i-1,rst%Po[i-1]);
}
else
if(Po[i-1]!=1)
{
for(RG int j=M-i+2;j<=M;++j)
Tag[j]=K;
}
}
int main()
{
R(N);
R(M);
R(K);
R(X);
scanf("%s",Buf);
for(RG int i=1;i<=M;++i)
Tag[i]=1;
Po[0]=1;
for(RG int i=1;i<=M;++i)
{
Po[i]=Po[i-1]*(unsigned long long)K;
if(Po[i]>X)
{
Dg(i,X);
break;
}
if(Po[i]==X)
{
for(RG int j=M;j>=M-i+1;--j)
Tag[j]=K;
break;
}
}
int ind=1;
for(RG int i=0;i<N;++i)
if(Buf[i]=='#')
{
scanf("%s",Su);
for(RG int j=0;j<26;++j)
Ap[j]=0;
for(RG int j=0;j<K;++j)
Ap[Su[j]-'a']=1;
for(RG int j=0;j<26;++j)
{
if(Ap[j])--Tag[ind];
if(Tag[ind]==0)
{
Buf[i]=j+'a';
break;
}
}
++ind;
}
puts(Buf);
return 0;
}