题解：P10735 [NOISG2019 Prelim] Square or Rectangle?

· · 题解

前言

这是一道交互题，不了解交互题的推荐先看洛谷交互题功能说明、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;
}

后记

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