自动搬运

查看原文

来自洛谷，原作者为

	small_john 说 P 话 || 不配拥有 8 级勾 || JO 厨 || 三体粉 || 安慕希玩家 || 壶关请看 https://www.luogu.me/paste/zrvg0p3s

搬运于2025-08-24 23:01:51，当前版本为作者最后更新于2025-05-30 17:03:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

感谢

思路

神仙狗屎题。

首先我们考虑最后选出的灯形如什么，其实一定是 $n$ 个横着的灯或者 $n$ 个竖着的灯。读者自证不难。

如果询问时有 $cnt_1$ 行存在横着的灯，$cnt_2$ 列存在竖着的灯，那么最后的返回值就是 $n(cnt_1+cnt_2)-cnt_1\times cnt_2$。

考虑一些随机化。

维护一个待确定的集合，此时想办法去确定这个集合里灯泡的方向。

再维护一个这些灯泡可能的状态集合（可以采用 bitset 记录），每次询问我们想尽量的缩减状态集合的大小。

在待确定的集合以及已经确定的灯泡中随机一些灯泡点亮，计算此方案在最劣时会剩下多少状态（即对每种询问的返回值计算有多少个状态会问出来这种返回值），然后取这个值最小的方案去询问。

询问过后将不符合返回值的状态删掉，此时可能会出现一些灯泡的方向确定。如果确定的是一个横向的灯泡这一行就没用了，删掉待确定集合中所有在这一行的点。是竖向的灯泡同理。

每次缩减完再加入一些点到待确定的集合中，使得状态集合的大小不超过一个阈值（大约为 $1000$）。

该算法在 $N=100$ 时，平均每次可以排除大约 $92\%$ 的情况，大约可以在 $75$ 次以内得出答案。

代码

实现得比较烂，仅供参考。

#include<bits/stdc++.h>
using namespace std;
mt19937 rnd(20101013);
const int N = 105,B = 1000,M = 400;
int n,ton[N*N];
bool ok[N][N],ok1[N],ok2[N];//是否被确定
bool ans[N][N];//横向还是纵向（1：横向，0：纵向）
bool vis[N][N],vis1[N],vis2[N];
bool out[N][N];
bool cmp(bitset<M> x,bitset<M> y)
{
	for(int i = 0;i<M;i++)
		if(x[i]<y[i]) return 1;
		else return 0;
	return 0;
}
inline void print()
{
	for(int i = 1;i<=n;i++,cout<<endl)
		for(int j = 1;j<=n;j++)
			cout<<out[i][j];
}
signed main()
{
	cin>>n;
	vector<int> v1,v2,s;//v1:未确定的行，v2：未确定的列 
	vector<pair<int,int>> s1;//当前去确定的位置
	vector<bitset<M>> s2;//当前可能的集合
	bitset<M> ts;
	s2.push_back(ts);
	while(1)
	{
		int cc = 0;
		for(int i = 1;i<=n;i++) cc+=ok1[i];
		if(cc==n)//每行都有已确定的横着的灯 
		{
			for(int i = 1;i<=n;i++)
				for(int j = 1;j<=n;j++)
					out[i][j] = 0;
			for(int i = 1;i<=n;i++)
				for(int j = 1;j<=n;j++)
					if(ok[i][j]&&ans[i][j]==1)
					{
						out[i][j] = 1;
						break;
					}
			cout<<"!"<<endl;
			print();
			return 0;
		}
		cc = 0;
		for(int i = 1;i<=n;i++) cc+=ok2[i];
		if(cc==n)//每列都有已确定的竖着的灯 
		{
			for(int i = 1;i<=n;i++)
				for(int j = 1;j<=n;j++)
					out[i][j] = 0;
			for(int j = 1;j<=n;j++)
				for(int i = 1;i<=n;i++)
					if(ok[i][j]&&ans[i][j]==0)
					{
						out[i][j] = 1;
						break;
					}
			cout<<"!"<<endl;
			print();
			return 0;
		}
		while(s2.size()*2<=B)//加入一些点 
		{
			vector<pair<int,int>> vec;
			for(int i = 1;i<=n;i++)
				for(int j = 1;j<=n;j++)
					vis[i][j] = 0;
			for(auto _:s1) vis[_.first][_.second] = 1;
			for(int i = 1;i<=n;i++)
				for(int j = 1;j<=n;j++)
				{
					if(ok[i][j]||ok1[i]||ok2[j]||vis[i][j]) continue;
					vec.push_back({i,j});
				}
			if(!vec.size()) break;
			int now = s1.size(),tmp = s2.size();
			s1.push_back(vec[rnd()%vec.size()]);
			for(int i = 0;i<tmp;i++)
			{
				ts = s2[i],ts.set(now);
				s2.push_back(ts);
			}
		}
		int T = 35;
		int now = 2e9;
		vector<int> mn;
		while(T--)//随机点亮的方案 
		{
			int mx = 0;
			s.resize(s1.size()); 
			for(int i = 0;i<s1.size();i++) s[i] = rnd()%2;
			for(auto z2:s2)
			{
				for(int i = 1;i<=n;i++) vis1[i] = vis2[i] = 0;
				for(int i = 0;i<s1.size();i++)
					if(s[i])
					{
						if(z2[i]) vis1[s1[i].first] = 1;
						else vis2[s1[i].second] = 1;
					}
				int cnt1 = 0,cnt2 = 0;
				for(int i = 1;i<=n;i++) cnt1+=vis1[i],cnt2+=vis2[i];
				ton[n*(cnt1+cnt2)-cnt1*cnt2]++;
				mx = max(mx,ton[n*(cnt1+cnt2)-cnt1*cnt2]);
			}
			if(mx<now) mn = s,now = mx;
			for(auto z2:s2)
			{
				for(int i = 1;i<=n;i++) vis1[i] = vis2[i] = 0;
				for(int i = 0;i<s1.size();i++)
					if(s[i])
					{
						if(z2[i]) vis1[s1[i].first] = 1;
						else vis2[s1[i].second] = 1;
					}
				int cnt1 = 0,cnt2 = 0;
				for(int i = 1;i<=n;i++) cnt1+=vis1[i],cnt2+=vis2[i];
				ton[n*(cnt1+cnt2)-cnt1*cnt2] = 0;
			}
		}
		for(int i = 1;i<=n;i++)
			for(int j = 1;j<=n;j++) out[i][j] = 0;
		for(int i = 0;i<s1.size();i++)
			if(mn[i]) out[s1[i].first][s1[i].second] = 1;
		cout<<"?"<<endl;
		print();
		int res;cin>>res;
		auto tmp = s2;s2.clear();
		for(auto z2:tmp)//找出那些合法的方案 
		{
			for(int i = 1;i<=n;i++) vis1[i] = vis2[i] = 0;
			for(int i = 0;i<s1.size();i++)
				if(mn[i])
				{
					if(z2[i]) vis1[s1[i].first] = 1;
					else vis2[s1[i].second] = 1;
				}
			int cnt1 = 0,cnt2 = 0;
			for(int i = 1;i<=n;i++) cnt1+=vis1[i],cnt2+=vis2[i];
			if(n*(cnt1+cnt2)-cnt1*cnt2==res) s2.push_back(z2);
		}
		for(int i = 0;i<s1.size();i++)//哪些点的方向被确定 
		{
			int sa = s2[0][i];
			for(auto z:s2)
			{
				int w = z[i]; 
				if(w!=sa) sa = -1;
			}
			if(sa!=-1)
			{
				int x = s1[i].first,y = s1[i].second;
				ok[x][y] = 1,ans[x][y] = sa;
				if(sa==0) ok2[y] = 1;
				else ok1[x] = 1;
			}
		}
		tmp = s2,s2.clear();
		for(auto z:tmp)//更新可能的状态 
		{
			ts.reset();
			int cnt = 0;
			for(int i = 0;i<s1.size();i++)
				if(ok[s1[i].first][s1[i].second]||(!ok1[s1[i].first]&&!ok2[s1[i].second]))//被确定的点不能被删去，以保证正确性 
					ts[cnt] = z[i],cnt++;
			s2.push_back(ts);
		}
		sort(s2.begin(),s2.end(),cmp);
		s2.erase(unique(s2.begin(),s2.end()),s2.end());
		vector<pair<int,int>> tmp2;
		for(int i = 0;i<s1.size();i++)//更新待确定的点 
			if(ok[s1[i].first][s1[i].second]||(!ok1[s1[i].first]&&!ok2[s1[i].second]))
				tmp2.push_back(s1[i]);
		s1 = tmp2;
	}
	return 0;
}