首先bitset用法链接:https://www.cnblogs.com/magisk/p/8809922.html
题解: 题目要判断哪个文本串是符合题意的.
限制:此字符串包含的信息用二进制表示后,可以找到一个u[i]使得对于每一个a[j] 进行运算后次位上都标记为1.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1010;
ll a[maxn],u[maxn];
string str[1010];
vector<int>v;
bitset<1010>info[1010],now;//储存每一个u[i]对应的能满足f的二进制串
string change(char x)//注意1转换为1000而不是0001,第一位为二进制的最低位,然后依次递推
{
if(x=='0') return (string)("0000");
else if(x=='1') return (string)("1000");
else if(x=='2') return (string)("0100");
else if(x=='3') return (string)("1100");
else if(x=='4') return (string)("0010");
else if(x=='5') return (string)("1010");
else if(x=='6') return (string)("0110");
else if(x=='7') return (string)("1110");
else if(x=='8') return (string)("0001");
else if(x=='9') return (string)("1001");
else if(x=='a') return (string)("0101");
else if(x=='b') return (string)("1101");
else if(x=='c') return (string)("0011");
else if(x=='d') return (string)("1011");
else if(x=='e') return (string)("0111");
else return (string)("1111");
}
int main()
{
freopen("filter.in", "r", stdin);
freopen("filter.out", "w", stdout);
int m,f,n,q;
cin>>m>>f;
for(int i=1;i<=f;i++){
cin>>a[i];
}
cin>>n;
for(int i=1;i<=n;i++){
cin>>str[i];
}
cin>>q;
for(int i=1;i<=q;i++){//记录每个u[i]可转变为的二进制串
cin>>u[i];
info[i].reset();
for(int j=1;j<=f;j++){
int pos=u[i]*a[j]%m;
info[i].set(pos,1);
}
}
for(int i=1;i<=n;i++){
string s;
int len=str[i].size();
for(int j=0;j<m/4;j++){
s+=change(str[i][j]);
}
if(m%4){
string w=change(str[i][len-1]);
for(int j=0;j<m%4;j++){
s+=w[j];
}
}
reverse(s.begin(),s.end());
bitset<1010>ww(s);//ww记录当前文本串的二进制串信息
for(int j=1;j<=q;j++){//题目要求:如果能找到一个u[i]使得每个f[j]运算后都标记为1,这个信息才是有记录的
now=ww&info[j];//我们需要判断ww是否包含info[i],只需这样与运算一下即可,
if(now.count()==info[j].count()){//然后判断一下1的个数是否相同
v.push_back(i-1);
break;
}
}
}
cout<<v.size()<<endl;
for(int i=0;i<v.size();i++)
cout<<v[i]<<' ';
cout<<endl;
return 0;
}
/*
23 4 3 5 7 11
3
effde7
c07902
0800c1
3 2 4 6
*/