[cf1552H]A Serious Referee

记$\Delta x=x_{2}-x_{1}+1$($\Delta y$类似),周长即$2(\Delta x+\Delta y-2)$

记$f(d)$为询问所有满足$d\mid i$的点$(i,j)$的结果,显然$f(d)=(\lfloor\frac{x_{2}}{d}\rfloor-\lfloor\frac{x_{1}-1}{d}\rfloor)\Delta y$

询问$d=1$,代入可得$f(1)=\Delta x\Delta y$,那么仅需要求出$\Delta x$或$\Delta y$之一即可

性质1:$f(d)=\frac{f(1)}{d}$当且仅当$d\mid \Delta x$

性质2:若$p=2^{k}\mid\mid \Delta x$(指$2^{k+1}\not\mid \Delta x$),则$|2f(2p)-\frac{f(1)}{p}|=\Delta y$

(前者比较显然,后者可以在$\Delta x$为奇数时感性理解,具体证明代入式子即可)

在$\{2^{0},2^{1},2^{2},...,2^{7}\}$中利用性质1二分即可找到$k$,这恰会询问3次

进一步的,得到$k$后$f(2p)$总已经被求出(除非$k=7$,但此时$f(2p)$总是0),也即可计算

询问次数恰好为4,可以通过

[cf1552H]A Serious Referee
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,x,S,ans;
 4 int query(int d){
 5     printf("? %d\n",n/d*n);
 6     for(int i=d;i<=n;i+=d)
 7         for(int j=1;j<=n;j++)printf("%d %d ",i,j);
 8     fflush(stdout);
 9     scanf("%d",&x);
10     return x;
11 }
12 int main(){
13     n=200,S=query(1),ans=0;
14     int l=0,r=7;
15     while (l<r){
16         int mid=(l+r+1>>1),s=query(1<<mid);
17         if ((s<<mid)==S)l=mid;
18         else r=mid-1,ans=s;
19     }
20     int y=abs((ans<<1)-(S>>l)),x=S/y;
21     printf("! %d\n",(x+y-2<<1));
22     return 0;
23 }
View Code

 

上一篇:DataLake — 批流一体化的追风者(2) -- Delta Lake核心原理解析


下一篇:Hibernate格式化SQL源码分析