题目描述
售票机是一种类似于ATM的设备，由克罗地亚铁路公司推出，以便人们更容易购买火车票。买票的第一步是选择旅程的目的地。目的地可以是提供的N个地点之一，包括当地和世界其他地区。您可以通过逐字母键入其名称来选择目的地。随着多输入字母，目的地的可能选择会减少。
屏幕上键盘的初始外观如上图所示。我们将它表示为长度为8的四个字符数组。 每当输入一个字母，键盘会改变其外观。只有在下一步中可以选择的字母才会保持活动状态（取决于仍可选择的目的地）。无法选择的剩余字母将替换为字符“*”。 编写一个程序，对于N个给定目的地和所选目的地的前几个字母（不是全部），输出当前键盘的外观。数据保证不会有已经输入完目的地的情况。
输入
第一行输入包含一个整数N（1≤N≤50）。表示目的地的个数。
接下来N行每行包含一个只由大写英文字母组成的字符串，每个字符串的长度都不超过100。每个字符串表示了一个目的地。
接下来一行包含了一个字符串，表示输入的目的地的前几个字母。
输出
输出四行，每行包含一个长度为8的字符串。表示指定格式下的当前键盘的外观。
样例输入
4
ZAGREB
SISAK
ZADAR
ZABOK
ZA样例输出
****B*D*
*G******
********
********解题思路
当场MLE，怪我乱开数组，以及非要用字典树....
字典树其实很好做的，你insert完，然后再find一下，最后标记一下就好了。
AC（MLE）代码
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int tree[1000005][30];//f**k
int n,cnt = 1,cnt1;
bool ans[30];
char s[105],c[105];
void insert(char *s){
int p = 0;
int len = strlen(s + 1);
for (int i = 1;i <= len;i ++){
int z = s[i] - 'A';
if (!tree[p][z])
tree[p][z] = ++ cnt;
p = tree[p][z];
}
}
void find(char *s){
int p = 0;
int len = strlen(s + 1);
for (int i = 1;i <= len;i ++){
int z = s[i] - 'A';
p = tree[p][z];
}
for (int i = 'A';i <= 'Z';i ++)
if (tree[p][i - 'A'])
ans[i - 'A'] = 1;
}
int main(){
//freopen("kartomat.in","r",stdin);
// freopen("kartomat.out","w",stdout);
scanf ("%d",&n);
for (int i = 1;i <= n;i ++){
scanf ("%s",s + 1);
insert(s);
}
scanf ("%s",c + 1);
find(c);
for (int i = 1;i <= 4;i ++){
for (int j = 1;j <= 8;j ++){
if ((i == 1 && j <= 3) || ((i == 4) && (j >= 6))){
printf("*");
continue;
}
if (ans[cnt1])
printf("%c",cnt1 + 'A');
else
printf("*");
cnt1 ++;
}
printf("
");
}
}然后就是暴力官方题解。
暴力枚举前缀，相同的话标记下一个字母即可
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int n,cnt1;
bool ans[30];
char s[105][105],c[105];
bool check(char *a,char *b){
for (int i = 1;i <= strlen(b + 1);i ++)
if (a[i] != b[i])
return 0;
return 1;
}
int main(){
//freopen("kartomat.in","r",stdin);
// freopen("kartomat.out","w",stdout);
scanf ("%d",&n);
for (int i = 1;i <= n;i ++)
scanf ("%s",s[i] + 1);
scanf ("%s",c + 1);
for (int i = 1;i <= n;i ++){
if (check(s[i],c))
ans[s[i][strlen(c + 1) + 1] - 'A'] = 1;
}
for (int i = 1;i <= 4;i ++){
for (int j = 1;j <= 8;j ++){
if ((i == 1 && j <= 3) || ((i == 4) && (j >= 6))){
printf("*");
continue;
}
if (ans[cnt1])
printf("%c",cnt1 + 'A');
else
printf("*");
cnt1 ++;
}
printf("
");
}
}