题解：洛谷P4424 [HNOI/AHOI2018] 寻宝游戏

洛谷首黑（虽然很水，并且小小地借助了题解），所以写一下题解作为巩固

洛谷

---

思路

非常容易注意到，对于位运算：

• 当你把某一位的数 $and$ $0$ ，就相当于把这一位数赋值为 $0$
• 当你把某一位的数 $or$ $1$ ，就相当于把这一位数赋值为 $1$
• 当你把某一位的数 $and$ $1$ 或者 $or$ $0$ 时，这一位的值不变

所以若要使最终某一位为 $0$，最后一个 $and$ $0$ 要出现在 $or$ $1$ 后面；为 $1$ 同理

后面这个转化借助了一下 StudyingFather 大神的题解思路：

我们设操作序列中 $or=0$ ，$and=1$ ；数字序列从下往上看得到的数为 $x$ ，操作序列从下往上看得到的数为 $y$

这样就将条件转化成：运算最后结果为 $0$ ，当且仅当 $x≤y$ ；为 $1$ 同理

遂将题目转化成求一个不等式组（把结果每一位拆开）

代码

#include<bits/stdc++.h>

using namespace std;

const long long mod=1000000007;

long long n,m,q;
string a[1005];

struct node
{
	string s;
	long long id;
	
	bool operator <(const node &a) const  //字典序排序
	{
		if(s!=a.s)
 		{
			return s>a.s;
		}
		return id<a.id;
	}  
} p[5005];
long long ans[5005];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	cin>>n>>m>>q;
	for(long long i=1;i<=n;i++)
	{
		cin>>a[i];
		for(long long j=0;j<m;j++)
		{
			a[i][j]-='0';
		}
		a[i][m]=1;
	}
	
	for(long long i=0;i<=m;i++)
	{
		p[i].id=i;
		for(long long j=n;j;j--)
		{
			ans[i]=(ans[i]*2+a[j][i])%mod;
			p[i].s+=a[j][i]; //预处理 
		}
	}
	
	ans[m]++;
	sort(p,p+m+1);
	p[m+1].id=m+1;
	
	while(q--)
	{
		string r;
		cin>>r;
		long long id1=0,id2=m+1;
		
		for(long long i=m;i;i--) //找上下界 
		{
			if(r[p[i].id]=='1')
			{
				id1=i;
				break;
			}
		}
		for(long long i=0;i<=m;i++)
		{
			if(r[p[i].id]=='0')
			{
				id2=i;
				break;
			}
		}
		
		if(id1>id2)
		{
			cout<<0<<"\n";
		}
		else
		{
			cout<<(ans[p[id1].id]-ans[p[id2].id]+mod)%mod<<"\n";
		}
	}
	
	return 0;
}