自动搬运

查看原文

来自洛谷，原作者为

	Resonate 你会忘记我吗 | 别看我啦已经AFO啦在家放假啦

搬运于2025-08-24 23:00:46，当前版本为作者最后更新于2024-08-08 10:25:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

这是一道交互题，不了解交互题的推荐先看洛谷交互题功能说明、OI Wiki对交互题的说明、P1733 猜数（IO交互版）<--交互入门1、P1947 猜数<--交互入门2。

题意

有 $N \times N (N \le 100)$ 的网格内有至少 $4\%$ 的涂色方格，它们组成一个矩形，你的任务是在最多 $33$ 次询问方格中的 $(X,Y)$ 方格是否涂色，并以此判断这个矩形是否为正方形。

思路

我们可以假设所有的矩形都是正方形，以 $N = 10$ 为例，则网格内至少有 $10 \times 10 \times 4 \% = 4$ 个涂色方块，因为它们都是正方形，故它的边长为 $2$，设这个值为 $p$。

对于网格中任意一点，都有可能成为涂色矩形中的一点，为了不浪费询问次数，我们可以每隔 $p$ 查询一次，这样可以最大化利用，如图所示，绿色方格为要询问的方格。

那为什么 $10$ 行和 $10$ 列不查呢？因为我们要减少询问次数，这个矩形在边缘的概率很小 (不排除毒瘤样例)。这样对于 $N = 100$ 的网格，最多只需询问 $16$ 次。

接下来，如果找到了某些点是涂色的，就用 $\min$ 和 $\max$ 找到在矩形中的左上点和右下点（也可以选择其他的），每一次询问，都是为了使左上的点更在左上，右下的点更在右下，为后面的寻找矩形的边缘奠定基础。

如果没有找到涂色的点，那这个矩形一定是在边缘（可以参考上图），我们再对边缘判断即可。

如果找到了，用二分找左上点上面的边和左边的边，找右下点下面的边，然后可以通过计算得知右边的边，此方法最多的询问次数为 $4 \times 4 + \log 20 \times 3 + 2$ 或 $5 \times 5 + \log 20 + 1$ 次，可以通过本题。

code

#include <bits/stdc++.h>
using namespace std;
extern "C" bool inside_shape(int x,int y);
int up(int x,int y,int s)//向上走，从 x+1 到 s
{
	int l=x+1,r=s,mid,ans=x;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(inside_shape(mid,y))
		{
			ans=mid;
			l=mid+1;
		}
		else
		{
			r=mid-1;
		}
	}
	return ans;
}
int down(int x,int y,int s)//向下走，从 s 到 x-1
{
	int l=s,r=x-1,mid,ans=x;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(inside_shape(mid,y))
		{
			ans=mid;
			r=mid-1;
		}
		else
		{
            l=mid+1;
		}
	}
	return ans;
}
int left(int x,int y,int s)//向左走，从 s 到 y-1
{
	int l=s,r=y-1,mid,ans=y;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(inside_shape(x,mid))
		{
			ans=mid;
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
	}
	return ans;
}
int right(int x,int y,int s)//向右走，从 y+1 到 s
{
	int l=y+1,r=s,mid,ans=y;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(inside_shape(x,mid))
		{
			ans=mid;
			l=mid+1;
		}
		else
		{
			r=mid-1;
		}
	}
	return ans;
}
extern "C" bool am_i_square(int N, int Q)
{
	int x_1=N+1,x_2=0,y_1=N+1,y_2=0;
	int plus=ceil(0.2*N);//对应上文变量 p
	for(int i=plus;i<N;i+=plus)
	{
		for(int j=plus;j<N;j+=plus)
		{
			if(inside_shape(i,j))
			{
				x_1=min(x_1,i);
				x_2=max(x_2,i);
				y_1=min(y_1,j);
				y_2=max(y_2,j);
			}
		}
	}
	if(x_2)
	{
		int new_x_1=0,new_y_1=0,new_x_2=0,new_y_2=0;
		new_x_1=down(x_1,y_1,x_1-plus+1);//x_1 和 y_1 是左上点
		new_y_1=left(x_1,y_1,y_1-plus+1);
		new_x_2=up(x_2,y_2,min(N,x_2+plus));//x_2 和 y_2 是右下点
		// new_y_2=right(x_2,y_2,min(N,y_2+plus)); 会超限哦~
		new_y_2=new_y_1+(new_x_2-new_x_1);
		return new_x_2<=N and (inside_shape(new_x_2,new_y_2) and (new_y_2==N or !inside_shape(new_x_2,new_y_2+1)));//要求：这个值不能大于 N，计算的右下点被涂色，右下点右边的点未涂色
	}
	if(inside_shape(N,N))//特判
	{
		return !inside_shape(N-plus,N) and !inside_shape(N,N-plus);
	}
	int new_x=0,new_y=0;
	for(int i=plus;i<N;i+=plus)
	{
		if(inside_shape(i,N))
		{
			new_x=down(i,N,i-plus+1);
			return !inside_shape(new_x+plus,N);//如果(i,N)存在，那么(找到的下边+p,N)一定不存在，如果返回为 1 就是这个矩形不是正方形，
		}
	}
	for(int i=plus;i<N;i+=plus)
	{
		if(inside_shape(N,i))
		{
			new_y=left(N,i,i-plus+1);
			return !inside_shape(N,new_y+plus);//同上
		}
	}
	return 0;
}

后记

交互题太好玩啦，本人千疮百孔的调试代码。