题解：CF1552H Guess the Perimeter

· · 题解

闲话：写了一个基于一点点数论的做法，交上去过了，然后发现题解区没有，而且貌似做法更简单，遂写题解。

首先注意到，选点集的全集可以求出面积，这样就把问题转化成了 3 次求矩形一条边的长度。

记矩阵水平于一行方向的边为长，另一边为宽。

不妨考虑一个看起来就很假的方法：选择一部分整行，答案与面积一定都是长的倍数，将得到的答案与面积取 \gcd，得到长的长度。

令选择的与矩阵有交的行数量为 w。

显然，这在 w 与矩阵宽不互质的时候会错。

如何解决这个问题呢？

可以刻画这个方法正确的时候，选择的行可以长什么样。

注意到，当宽为奇数时，只要隔一行选一行就是对的。

证明：设矩形宽为 b，其一定为奇数，则在这种情况下 b=2w+1 或 b=2w-1。

利用定理 \gcd(a,b)=\gcd(a,a-b)：

证毕。

当宽为偶数怎么办呢？

注意到当宽为偶数时，可以把原问题进行放缩，即删掉所有未被选择的行，把这一次的答案当成新矩形的面积，转化成子问题，这样对正确性一定不会有影响。

在我们不知道宽奇偶性的情况下，也就是对于步长为 2^k 的所有情况都查一次，找到尽可能大的 k 满足查出的答案不为 0，然后求 \gcd。

因为 k_{max}+1 的答案为 0，易证放缩到 k_{max} 时宽度为奇数，根据刚才奇数的想法，这样做就是对的。

这样类似于一个倍增，次数是 O(n)=O(\frac{n}{2})+1 即 O(n)=\log n 的，可以做到 7 次。

然而题目要求 3 次，不难想到做法应该是 O(\log \log n) 级别的。

我们刚才倍增每次查的其实是相互独立的，并且注意到答案具有单调性，即只需要二分出最后一个答案不为 0 的 k 即可，可以做到 3 次。

加上一开始查的面积，一共是 4 次。

核心代码：

namespace Junounly
{
    int ask(int x)
    {
        cout<<"? "<<' '<<200*(200/x)<<endl;
        for(int i=x;i<=200;i+=x)
            for(int j=1;j<=200;j++)
                cout<<i<<' '<<j<<' ';
        cout<<endl;
        int res;
        cin>>res;
        return res;
    }
    void main()
    {
        int sum=ask(1),l=0,r=7,res=114514;
        for(;l<r;)
        {
            int mid=(l+r+1)>>1,now=ask(1<<mid);
            if(now) l=mid,res=now;
            else r=mid-1;
        }
        int A=114514;
        if(res) A=__gcd(res,sum);
        else A=1;
        cout<<"! "<<(A+sum/A-2)*2<<endl;
    }
}