自动搬运

查看原文

来自洛谷，原作者为

	DeepSeaSpray **

搬运于2025-08-24 23:00:52，当前版本为作者最后更新于2024-10-04 22:52:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

不太理解题意的可以上 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})$ 的，常数优秀，可以通过本题。

#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(){
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	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;
}