题解：P10746 [SEERC2020] Codenames

· · 题解

不太理解题意的可以上 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;
}