[loj2494]寻宝游戏

将$n+1$个数字（还有0）标号为$[0,n]$，那么定义$a_{i,j}$表示第j个数上第i位上的值，如果第$i-1$个数与第$i$个数之间的运算符为与，那么令$b_{i}=1$，否则$b_{i}=0$，特别的，$b_{0}=1$（因此很明显有$b_{0}\ne a_{0,0}$，即$b\ne a_{i}$）

考虑对于第i位，那么结果其实就是最大的$a_{i,j}\ne b_{j}$的j上的$a_{i,j}$，如果这一位结果为0，当且仅当$a_{i}<b$（转化为二进制数，0为最低位），同理这一位结果为1，当且仅当$a_{i}>b$，那么我们就可以求出b的范围，又因为每一个b唯一对应一种方案，因此b的数量即为方案数量（细节上，由于$a_{i,0}<b_{0}$，因此$ai<b$等价于去掉最后一位后$ai=b$）

那么预处理将所有ai排序，然后枚举即可求出最小值和最大值，相减即为答案

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 5005

 4 #define mod 1000000007

 5 struct ji{

 6     int a[1005];

 7 }ans,a[N];

 8 int n,m,q,id[N],rk[N];

 9 char s[N];

10 bool cmp(int x,int y){

11     for(int i=1000;i;i--)

12         if (a[x].a[i]!=a[y].a[i])return a[x].a[i]<a[y].a[i];

13     return 0;

14 }

15 int main(){

16     scanf("%d%d%d",&n,&m,&q);

17     for(int i=1;i<=n;i++){

18         scanf("%s",s);

19         for(int j=0;s[j];j++)a[j].a[i]=s[j]-'0';

20     }

21     for(int i=0;i<m;i++)id[i]=i;

22     sort(id,id+m,cmp);

23     for(int i=0;i<m;i++)rk[id[i]]=i;

24     for(int i=1;i<=q;i++){

25         scanf("%s",s);

26         int x=-1,y=m;

27         for(int j=0;s[j];j++)

28             if (s[j]=='0')x=max(x,rk[j]);

29             else y=min(y,rk[j]);

30         if (x<0)ans=a[id[y]];

31         if (y==m)

32             for(int j=1;j<=n;j++)ans.a[j]=1-a[id[x]].a[j];

33         if ((x>=0)&&(y<m))

34             if (!cmp(id[x],id[y]))memset(ans.a,0,sizeof(ans.a));

35             else

36                 for(int j=1,p=0;j<=1000;j++){

37                     ans.a[j]=a[id[y]].a[j]-p-a[id[x]].a[j];

38                     p=(ans.a[j]<0);

39                     ans.a[j]+=p*2;

40                 }

41         ans.a[0]=0;

42         for(int j=1000;j;j--)ans.a[0]=(ans.a[0]*2+ans.a[j])%mod;

43         printf("%d\n",(ans.a[0]+(y==m))%mod);

44     }

45 }

巴特西

[loj2494]寻宝游戏

最新文章

热门文章