不太理解题意的可以上 CodeForces 看原版英文题面：Link 。
上面也有英文原版题解。
首先我们直接令 $g = 9$ 即可，因为 r 最多只有 $9$ 个，而翻完就会自动停止。
接着我们考虑转化一下问题。
首先我们必须翻出所有的 r，并且不能翻出其他的小写字母，对于大写字母翻了也没事。
那么我们可以考虑转化成一个字符串匹配的问题。
对于输入的字符串，我们将它们的所有前缀（取前缀是因为可能翻到某一步就停止了）作为文本串。并将一个字母对应的位置设成 1，其余的设成 0，z 不做处理。
例如：azcex 对应 1010100000000000000000010。
对于输入的表格，我们将它们作为模式串。具体来说，r 对应 1，其余小写字母对应 0，大写字母对应通配符 ?。
例如：rnnnB rnBBb nrBrr RBBrR rxnnb 对应：1000?10??001?11???1?10000。
我们的任务是对于每一个模式串找到与之匹配的文本串。
我们考虑这一件事情，设 $cnt_0$，$cnt_1$，$cnt_q$ 分别表示 模式串中为 0，1，? 的数量。
由于平均值原理：
$$
\min(cnt_0,cnt_1,cnt_q) \leq \frac{cnt_0+cnt_1+cnt_q}{3} = \frac{25}{3} \leq 9
$$
所以如果我们有分别与 $cnt_0$，$cnt_1$，$cnt_q$ 相关的算法，我们就可以在较优秀的时间复杂度内解决问题。
与 $cnt_q$ 相关
暴力枚举通配符的取值即可。实现上可以用枚举子集简单实现。
单词操作时间复杂度 $O(2^9)$。
与 $cnt_1$ 相关
我们考虑如何数出一个模式串的与之匹配的文本串。
对于通配符我们并不好处理，由于文本串实际上是二进制数，这启发我们使用高维前缀和，直接令通配符取值 1。
但是这样我们模式串中要求为 1 的位就无法达成限制，所以我们考虑组合-容斥掉这一部分。
具体来说，我们把一些为 1 的位设成 0，设这样的位有 $t$ 个，那么组合-容斥系数即为 $(-1)^t$。
组合-容斥可以用枚举子集简单实现。
如果存在这样的文本串，我们还需要考虑如何求出这一个文本串。
我们对于每一个 ? 先将其设为 0 计算对应文本串个数，如果存在，那么这一位填 0，否则这一位填 1。
这一部分可以用 Lowbit 简单实现。
单次操作时间复杂度 $O(18 \times 2^9)$
与 $cnt_0$ 相关
与 $cnt_1$ 的部分本质相同，各位可以自行思考，我将修改过的部分写在下面。
我们使用高维后缀和，直接令通配符取值 0。
组合-容斥掉要求为 0 的部分。
我们把一些为 0 的位设成 1，设这样的位有 $t$ 个，那么组合-容斥系数即为 $(-1)^t$。
如果存在这样的文本串，我们还需要考虑如何求出这一个文本串。
我们对于每一个 ? 先将其设为 1 计算对应文本串个数，如果存在，那么这一位填 1，否则这一位填 0。
其中高维前缀和预处理时间复杂度是 $O(2^{25})$ 的，常数优秀，可以通过本题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| #include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
const int maxm=30;
const int maxk=25;
const int maxs=1<<maxk;
int n,m;
char str[maxn+5][maxm+5];
int id[maxs+5];
int f[maxs+5],g[maxs+5];
int tmpq,tmp0,tmp1;
int cntq,cnt0,cnt1;
inline char Getch(){
char ch=getchar();
while(!(('a'<=ch&&ch<='z')||('A'<=ch&&ch<='Z')))
ch=getchar();
return ch;
}
inline int Lowbit(int x){return x&(-x);}
inline int Count0(){
int res=0;
for(int s=tmp0;;s=(s-1)&tmp0){
if(__builtin_popcount(s)&1) res-=g[s|tmp1|tmpq];
else res+=g[s|tmp1|tmpq];
if(!s) break;
}
return res;
}
inline int Count1(){
int res=0;
for(int s=tmp1;;s=(s-1)&tmp1){
if((cnt1-__builtin_popcount(s))&1) res-=f[s|tmpq];
else res+=f[s|tmpq];
if(!s) break;
}
return res;
}
signed main(){
int len,tmp;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",str[i]);
len=strlen(str[i]),tmp=0;
for(int j=0;j<len;j++){
if(str[i][j]!='z'){
tmp|=1<<(str[i][j]-'a');
id[tmp]=i;
f[tmp]++,g[tmp]++;
}
}
}
for(int i=0;i<maxk;i++){
for(int j=0;j<maxs;j++){
if((j>>i)&1) f[j]+=f[j^(1<<i)];
else g[j]+=g[j^(1<<i)];
}
}
char ch;
int res;
scanf("%d",&m);
while(m--){
tmpq=tmp0=tmp1=0;
cntq=cnt0=cnt1=0;
for(int i=0;i<maxk;i++){
ch=Getch();
if('A'<=ch&&ch<='Z') tmpq|=1<<i,cntq++;
else if(ch=='r') tmp1|=1<<i,cnt1++;
else tmp0|=1<<i,cnt0++;
}
if(cnt0==min({cnt0,cnt1,cntq})){
int s=tmpq;tmpq=0;
if(Count0()){
for(;s;s-=Lowbit(s)){
tmpq+=Lowbit(s);
if(!Count0()) tmpq-=Lowbit(s);
}
res=tmp1|tmpq;
}
else res=-1;
}
else if(cnt1==min({cnt0,cnt1,cntq})){
int s=tmpq;
if(Count1()){
for(;s;s-=Lowbit(s)){
tmpq-=Lowbit(s);
if(!Count1()) tmpq+=Lowbit(s);
}
res=tmp1|tmpq;
}
else res=-1;
}
else{
res=-1;
for(int s=tmpq;;s=(s-1)&tmpq){
if(id[tmp1|s]) res=tmp1|s;
if(!s) break;
}
}
if(~res) printf("%s 9\n",str[id[res]]);
else puts("IMPOSSIBLE");
}
return 0;
}
|