M_sea

洛谷4424 [HNOI2018]寻宝游戏
LuoguBZOJ分析神仙题。按位考虑每一位。显然,只要$\mathrm{or\ 1}$,这一位就会变成$1$;只...
扫描右侧二维码阅读全文
28
2019/02

洛谷4424 [HNOI2018]寻宝游戏

Luogu

BZOJ

分析

神仙题。

按位考虑每一位。显然,只要$\mathrm{or\ 1}$,这一位就会变成$1$;只要$\mathrm{and\ 0}$,这一位就会变成$0$。

类似的,$\mathrm{or\ 0}$与$\mathrm{and\ 1}$都没有什么影响。

那么把$\mathrm{or}$写成$0$,$\mathrm{and}$写成$1$。

这样子的话,如果某个数的前面的操作符与某一位相同,那么这一位就等价于没有进行操作,否则可以直接知道这一位的结果。

假设只有一个二进制位,那么就是一个长为$n$的串$x$,和一个长为$n$的串$op$。

可以发现,如果$x>op$,那么这一位为$1$,否则为$0$。

这样子的话,就可以算出$x\leq op<y$,答案就是$y-x$。

使用基数排序把每一位按照其二进制的值排好序,这样子就可以直接找到结果为$0$的最大值和结果为$1$的最小值。

具体实现及细节见代码。

代码


//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

const int N=5000+10;
const int mod=1000000007;

char str[N];
int a[N],b[N],c[2],s[N],t[N],pw[N];

int main() {
    int n,m,q; scanf("%d%d%d",&n,&m,&q);
    pw[0]=1; for (re int i=1;i<=n;++i) pw[i]=pw[i-1]*2%mod;
    for (re int i=1;i<=m;++i) a[i]=i;
    for (re int i=1;i<=n;++i) {
        scanf("%s",str+1); c[0]=0,c[1]=m;
        for (re int j=1;j<=m;++j) {
            if (str[j]=='0') ++c[0];
            else s[j]=(s[j]+pw[i-1])%mod;
        }
        for (re int j=m;j>=1;--j) b[c[str[a[j]]-'0']--]=a[j];
        for (re int j=1;j<=m;++j) a[j]=b[j];
    }
    for (re int i=1;i<=m;++i) t[i]=s[a[i]]; t[m+1]=pw[n];
    while (q--) {
        scanf("%s",str+1);
        int l=0,r=m+1;
        for (re int i=m;i>=1;--i)
            if (str[a[i]]=='0') { l=i; break; }
        for (re int i=1;i<=m;++i)
            if (str[a[i]]=='1') { r=i; break; }
        if (l>r) puts("0");
        else printf("%d\n",(t[r]-t[l]+mod)%mod);
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 02 PM

发表评论