专栏文章

题解：CF1552H Guess the Perimeter

JJunounly
CF1552H题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipl42xu
此快照首次捕获于
2025/12/03 13:46
3 个月前
此快照最后确认于
2025/12/03 13:46
3 个月前
查看原文
闲话：写了一个基于一点点数论的做法，交上去过了，然后发现题解区没有，而且貌似做法更简单，遂写题解。
首先注意到，选点集的全集可以求出面积，这样就把问题转化成了 33 次求矩形一条边的长度。
记矩阵水平于一行方向的边为长，另一边为宽。
不妨考虑一个看起来就很假的方法：选择一部分整行，答案与面积一定都是长的倍数，将得到的答案与面积取 gcd⁡\gcd，得到长的长度。
令选择的与矩阵有交的行数量为 ww。
显然，这在 ww 与矩阵宽不互质的时候会错。
如何解决这个问题呢？
可以刻画这个方法正确的时候，选择的行可以长什么样。
注意到，当宽为奇数时，只要隔一行选一行就是对的。
证明：设矩形宽为 bb，其一定为奇数，则在这种情况下 b=2w+1b=2w+1 或 b=2w−1b=2w-1。
利用定理 gcd⁡(a,b)=gcd⁡(a,a−b)\gcd(a,b)=\gcd(a,a-b)：
  • 若 b=2w−1b=2w-1，gcd⁡(w,b)=gcd⁡(w,2w−1)=gcd⁡(w,w−1)=1\gcd(w,b)=\gcd(w,2w-1)=\gcd(w,w-1)=1。
  • 若 b=2w+1b=2w+1，gcd⁡(w,b)=gcd⁡(w,2w+1)=gcd⁡(w,w+1)=1\gcd(w,b)=\gcd(w,2w+1)=\gcd(w,w+1)=1。
证毕。
当宽为偶数怎么办呢？
注意到当宽为偶数时，可以把原问题进行放缩，即删掉所有未被选择的行，把这一次的答案当成新矩形的面积，转化成子问题，这样对正确性一定不会有影响。
在我们不知道宽奇偶性的情况下，也就是对于步长为 2k2^k 的所有情况都查一次，找到尽可能大的 kk 满足查出的答案不为 00，然后求 gcd⁡\gcd。
因为 kmax+1k_{max}+1 的答案为 00，易证放缩到 kmaxk_{max} 时宽度为奇数，根据刚才奇数的想法，这样做就是对的。
这样类似于一个倍增，次数是 O(n)=O(n2)+1O(n)=O(\frac{n}{2})+1 即 O(n)=log⁡nO(n)=\log n 的，可以做到 77 次。
然而题目要求 33 次，不难想到做法应该是 O(log⁡log⁡n)O(\log \log n) 级别的。
我们刚才倍增每次查的其实是相互独立的，并且注意到答案具有单调性，即只需要二分出最后一个答案不为 00 的 kk 即可，可以做到 33 次。
加上一开始查的面积，一共是 44 次。
核心代码：
C
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;
    }
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...