题意 给你 nn 个长度为 mm 的 0101 串
你可以在每个串前面加一个运算符 ∧∧ 或 ∨,∨ , 分别表示 anda n d 和 oro r 运算
每次询问一个长度为 mm 的 0101 串 ,, 问有多少总操作序列能得到这个串
题解 因为是二进制数 ,, 所以考虑按位处理( ii 表示第 ii 个数字 ,j, j 表示第 jj 位)
1.1.
0∨1=1,1∨1=10 ∨ 1 = 1 , 1 ∨ 1 = 1也就是说如果第 jj 位是 00 且 ii 前面的运算符是 ∧,∧ , 那么不管前面是什么最后的运算结果都确定了是 00 (另外一种情况同理)
0∧0=0,1∧0=00 ∧ 0 = 0 , 1 ∧ 0 = 0
2.2.
0∨0=0,1∨0=10 ∨ 0 = 0 , 1 ∨ 0 = 1也就是说如果第 jj 位是 00 且 ii 前面的运算符是 ∨,∨ , 那么不管前面是什么最后的运算结果都不会发生改变(另外一种情况同理)
0∧1=0,1∧1=10 ∧ 1 = 0 , 1 ∧ 1 = 1
考虑把操作序列转化成 0101 序列 (∨→0,∧→1)( ∨ → 0 , ∧ → 1 )
可以观察到
如果 ii 前面的运算符和第 jj 位相同那么运算结果就不会改变设最后一位是最高位
否则的话运算结果也是可以直接得出的
把第 jj 位的 0101 串提出来得到一个长度是 nn 的二进制数 xx
因为要使得第 jj 位运算结果是 11 则最后一个 ∨1∨ 1 操作的位置一定要在 ∧0∧ 0 后面
转化一下就是就要求 x>x > 操作串
e.ge . g
x=1011,op=0011,x>opx = 1011 , o p = 0011 , x > o p那么这道题就成功的转化为一个比大小的题目了
0∨1∨0∧1∧1=10 ∨ 1 ∨ 0 ∧ 1 ∧ 1 = 1
x=1011,op=1011,x≤opx = 1011 , o p = 1011 , x ≤ o p
0∧1∨0∧1∧1=00 ∧ 1 ∨ 0 ∧ 1 ∧ 1 = 0
每一位按照其二进制数的值排序
判断一下每一位二进制数和 opo p 的大小关系
如果有解最后可以得到 x≤op
#include
#define fp(i,a,b) for(register int i=a,I=b+1;
iI;
--i)
#define go(u) for(register int i=fi[u],v=e[i].to;
i;
v=e[i=e[i].nx].to)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
templateinline bool cmax(T&a,const T&b){return ainline bool cmin(T&a,const T&b){return a>b?a=b,1:0;
}
using namespace std;
const int N=5005,P=1e9+7;
typedef int arr[N];
int n,m,q,c[2];
arr a,b,s,t,Mi;
char p[N];
inline int pls(int a,int b){return a+=b,a【[HNOI2018]寻宝游戏】inline int sub(int a,int b){return a-=b,a<0?a+P:a;
}
int main(){
#ifndef ONLINE_JUDGE
file("s");
#endif
scanf("%d%d%d\n",&n,&m,&q);
Mi[1]=1;
fp(i,2,n+1)Mi[i]=(Mi[i-1]<<1)%P;
fp(i,1,m)a[i]=i;
fp(i,1,n){
gets(p+1);
c[0]=0,c[1]=m;
fp(j,1,m)p[j]=='1'?s[j]=pls(s[j],Mi[i]):++c[0];
fd(j,m,1)b[c[p[a[j]]-48]--]=a[j];
swap(a,b);
}
fp(i,1,m)t[i]=s[a[i]];
register int up,dw;
t[m+1]=Mi[n+1];
while(q--){
gets(p+1);
up=m+1,dw=0;
fd(i,m,1)if(p[a[i]]=='0'){dw=i;
break;
}
fp(i,1,m)if(p[a[i]]=='1'){up=i;
break;
}
printf("%d\n",up 
