NC53713. 富豪凯匹配串
描述
输入描述
第一行输入n,m
接下来n行，每行输入一个长度为m的01串表示一个文本串。
第n+2行输入Q
接下来Q行，每行输入一个长度为m的字符串(只包含'0','1','_')。
1<=n,m<=1000,1<=Q<=3000。
输出描述
对于每次询问，输出n个文本串中有多少个与当前询问的串匹配。
示例1
输入:
5 6 101101 011011 100110 111000 101111 2 1011_1 1__1__
输出:
2 3
说明:
第一次询问：有101101，101111与1011_1匹配C++14(g++5.4) 解法, 执行用时: 132ms, 内存消耗: 736K, 提交时间: 2019-10-11 23:16:32
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
bitset<N>c[N],A,B;
int n,m,q;
char s[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",s);
for(int j=0;j<m;j++)c[i][j]=s[j]-'0';
}
scanf("%d",&q);
while(q--){
scanf("%s",s);
for(int i=0;i<m;i++){
if(s[i]=='0')A[i]=1,B[i]=0;
else if(s[i]=='1')A[i]=1,B[i]=1;
else A[i]=0,B[i]=0;
}
int ans=0;
for(int i=1;i<=n;i++){
if((A&c[i])==B)ans++;
}
printf("%d\n",ans);
}
}
C++11(clang++ 3.9) 解法, 执行用时: 250ms, 内存消耗: 4504K, 提交时间: 2019-10-13 20:54:40
#include<bits/stdc++.h>
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
bitset<1005>a[1005][2],b;
int main(){
int n,m,q; string s; cin>>n>>m; rep(i,0,n){
cin>>s; rep(j,0,m) a[j][s[j]-'0'].set(i);
} cin>>q; while(q--){
cin>>s; rep(i,0,n) b.set(i); rep(i,0,m){
if(s[i]=='_') continue;
b=b&a[i][s[i]-'0'];
} cout<<b.count()<<'\n';
}
}