证明了自己思维不行。记一记自己的垃圾做法。
首先是场上做法：考虑按位枚举钦定一个前缀，这样从最优化问题转化成判定性问题，更好处理。
称钦定的前缀 01 状态为 \(mask\)，询问串和 \(mask\) 匹配的下标集合为 \(goal\)。考虑按操作顺序从后往前添加操作，设当前前缀还没有跟 \(mask\) 匹配的下标为 \(S\) 的一个子集。那么如果我们要 DP 的话肯定是找到一个满足 \(S\) 的下标集合中没有失配的，并且不能全是 \(\texttt{-}\) 操作，这样的话就可以转移到 \(S\) 的一个真子集，我们最后的目标是判断是否能从全集转移到 \(goal\) 的某一个子集。
简单思考一下，我们发现全集能转移到 \(goal\) 的子集的一个充要条件就是每一个不是 \(goal\) 的子集的点必须有一条指向其真子集的边。
然而场上就只会每次询问高维后缀和来找到“没有失配且不全是问号”的这种操作。
#include <cstdio>
#include <algorithm>
using namespace std;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int N=100003;
int f[1<<20],g[1<<20];
char str[N][22];
char qry[22];
int n,m,q;
int msk01[N],msk_[N];
bool check(int msk,int x){
int mm=(1<<x)-1;
for(int i=0;i<(1<<x);++i) f[i]=g[i]=0;
for(int i=1;i<=n;++i){--f[mm^((msk01[i]^msk)&(mm^msk_[i])&mm)];++f[msk_[i]&mm];}
for(int i=1;i<(1<<x);i<<=1)
for(int j=0;j<(1<<x);j+=(i<<1))
for(int k=j;k<(j|i);++k) f[k]+=f[k|i];
int goal=0;
for(int j=0;j<x;++j)
if((qry[j]^48)==(msk>>j&1)) goal|=(1<<j);
for(int s=0;s<(1<<x);++s){
if((s&goal)==s) continue;
if(f[s]>=0) return 0;
}
return 1;
}
int main(){
m=read();n=read();q=read();
bool fl=1;
for(int i=1;i<=n;++i){
scanf("%s",str[i]);
for(int j=0;j<m;++j){
if(str[i][j]=='-') fl=0,msk_[i]|=(1<<j);
else{
if(str[i][j]=='1') msk01[i]|=(1<<j);
}
}
}
if(fl){
bool fl=1;
int mx=0;
for(int i=1;i<=n;++i){
int cur=0;
for(int j=0;j<m;++j)
if(str[i][j]=='1') cur|=(1<<(m-j-1));
mx=max(mx,cur);
}
for(int i=1;i<=q;++i){
scanf("%s",qry);
int res=0;
for(int j=0;j<m;++j)
if(qry[j]=='1') res|=(1<<(m-j-1));
res=max(res,mx);
for(int j=m-1;~j;--j)
if(res>>j&1) putchar('1');
else putchar('0');
putchar('\n');
}
return 0;
}
for(int i=1;i<=q;++i){
scanf("%s",qry);
int res=0;
for(int j=0;j<m;++j)
if(check(res|(1<<j),j+1)) res|=(1<<j);
for(int j=0;j<m;++j)
putchar((res>>j&1)^48);
putchar('\n');
}
return 0;
}
导向正确想法的关键是注意到这个 \(mask\) 中的 \(0\) 其实可以换成 \(?\)。这是因为我们贪心的过程保证了最终答案至少前 \(x-1\) 位不会比 \(mask\) 的前 \(x-1\) 更优。
于是我们发现高维前缀和的部分可以拎到外面去了，如下：
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int N=100003;
vector<int> f[23],g[23];
char str[24];
char qry[24];
int n,m,q;
bool check(int msk,int x){
int goal=0;
for(int i=0;i<x;++i) if((qry[i]^48)==(msk>>i&1)) goal|=(1<<i);
for(int i=0;i<(1<<x);++i){
if((i&goal)==i) continue;
if(g[x][i&msk]<=f[x][i]) return 0;
}
return 1;
}
void FWT(int x){
for(int i=1;i<(1<<x);i<<=1)
for(int j=0;j<(1<<x);j+=(i<<1))
for(int k=j;k<=(j|i);++k){
f[x][k]+=f[x][k|i];
g[x][k]+=g[x][k|i];
}
}
int main(){
m=read();n=read();q=read();
for(int i=1;i<=m;++i) f[i]=g[i]=vector<int>(1<<i,0);
for(int i=1;i<=n;++i){
scanf("%s",str);
int num=0,cur=0;
for(int j=0;j<m;++j){
if(str[j]=='-') num|=(1<<j);
if(str[j]!='0') cur|=(1<<j);
}
for(int x=1;x<=m;++x){
++f[x][num&((1<<x)-1)];
++g[x][cur&((1<<x)-1)];
}
}
for(int i=1;i<=m;++i) FWT(i);
for(int i=1;i<=q;++i){
scanf("%s",qry);
int res=0;
for(int j=0;j<m;++j)
if(check(res|(1<<j),j+1)) res|=(1<<j);
for(int j=0;j<m;++j)
putchar((res>>j&1)^48);
putchar('\n');
}
return 0;
}
我们进一步发现 \(g\) 是高维前缀和数组关于子集有单调性，我们要尽可能取小的才容易满足代码中 \(f\leq g\) 的条件，我们可以发现至多需要 check \(i\cap msk\) 比 \(i\) 小 1 的情况。
于是高维前缀或一下记录是否违反限制的 \(i\) 都是 \(goal\) 的子集。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int N=100003;
vector<int> f[23],g[23],h[23];
char str[24];
char qry[24];
int n,m,q,goal;
bool check(int msk,int x){
return (goal&h[x][msk])==h[x][msk];
}
void FWT(int x){
for(int i=1;i<(1<<x);i<<=1)
for(int j=0;j<(1<<x);j+=(i<<1))
for(int k=j;k<=(j|i);++k){
f[x][k]+=f[x][k|i];
g[x][k]+=g[x][k|i];
}
for(int i=0;i<(1<<x);++i){
if(g[x][i]<=f[x][i]) h[x][i]=i;
for(int j=0;j<x;++j)
if(g[x][i]<=f[x][i|(1<<j)]) h[x][i]|=(1<<j);
}
for(int i=1;i<(1<<x);i<<=1)
for(int j=0;j<(1<<x);j+=(i<<1))
for(int k=j;k<=(j|i);++k) h[x][k|i]|=h[x][k];
}
int main(){
m=read();n=read();q=read();
for(int i=1;i<=m;++i) f[i]=g[i]=h[i]=vector<int>(1<<i,0);
for(int i=1;i<=n;++i){
scanf("%s",str);
int num=0,cur=0;
for(int j=0;j<m;++j){
if(str[j]=='-') num|=(1<<j);
if(str[j]!='0') cur|=(1<<j);
}
for(int x=1;x<=m;++x){
++f[x][num&((1<<x)-1)];
++g[x][cur&((1<<x)-1)];
}
}
for(int i=1;i<=m;++i) FWT(i);
for(int i=1;i<=q;++i){
scanf("%s",qry);
int res=0;
goal=0;
for(int j=0;j<m;++j){
if(qry[j]=='1') goal|=(1<<j);
if(check(res|(1<<j),j+1)) res|=(1<<j);
else goal^=(1<<j);
}
for(int j=0;j<m;++j)
putchar((res>>j&1)^48);
putchar('\n');
}
return 0;
}
时间复杂度 \(O(nm+qm+2^m m)\)。