BZOJ5285 & 洛谷4424 & UOJ384：[HNOI/AHOI2018]寻宝游戏—

BZOJ5285 & 洛谷4424 & UOJ384：[HNOI/AHOI2018]寻宝游戏——题解

阅读量：7000 次

发布时间：2019-06-27

本文共 1272 字，大约阅读时间需要 4 分钟。

洛谷的题解已经很把思想过程完备地表达出来了：

感觉比官方题解说的还清楚。

那么问题就是我们到底应该如何实现这个算法呢？

一个直观的想法是把每一位的数全部处理出来，然后排个序，之后根据给定的序列每位的0/1查找出答案应当在什么区间内即可。

但是很玄妙的是我们排序要对原来的数进行排序，不能对其取模之后的答案排序。

于是这里用了题解的写法，排序用基数排序根据读入直接完成。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;const int p=1e9+7;const int M=5005;int n,m,q,base[M],w[M],a[M],b[M],c[M],t[M];char s[M];int main(){ scanf("%d%d%d",&n,&m,&q); base[1]=1; for(int i=2;i<=n+1;i++)base[i]=base[i-1]*2%p; for(int i=1;i<=m;i++)a[i]=i; for(int i=1;i<=n;i++){ scanf("%s",s+1);c[0]=0;c[1]=m; for(int j=1;j<=m;j++){ if(s[j]=='1')w[j]=(w[j]+base[i])%p; else c[0]++; } for(int j=m;j>=1;j--){ b[c[s[a[j]]-'0']--]=a[j]; } swap(a,b); } for(int i=1;i<=m;i++)t[i]=w[a[i]]; t[m+1]=base[n+1]; for(int i=1;i<=q;i++){ scanf("%s",s+1); int l=0,r=m+1; for(int j=m;j>=1;j--){ if(s[a[j]]=='0'){l=j;break;} } for(int j=1;j<=m;j++){ if(s[a[j]]=='1'){r=j;break;} } if(l>r)puts("0"); else printf("%d\n",(t[r]-t[l]+p)%p); } return 0;}