P8111 [Cnoi2021]区间题解

WYXkk · 2022-02-04 23:08:12 · 题解

不困难但非常有意思的题目。

我们先考虑一下，假设第一次调用了 Query(pos)：

返回 -1：最快的方法显然是把 [1,n-pos] 的方法搬到 [pos+1,n] 上。
返回 0：最快的方法是在 [1,pos] 和 [pos,n] 上分别二分左右端点。(*)
返回 1：最快的方法显然是当作 [1,pos-1] 的问题做。

(*) 似乎不太显然，此处给出证明：
再调用 Query(pos) 已经没有意义；对于 u<pos 调用 Query(u) 只能得到待猜区间左端点和 u 的大小关系（大于或小于等于）；对于 u>pos 调用 Query(u) 只能得到待猜区间右端点和 u 的大小关系（小于或大于等于）。
这样原问题就变成了两个互不影响的问题（分别猜测左右端点），每个问题都可以用一次询问来得到两种答案之一，因此至少需要 \lceil\log_2|L|\rceil+\lceil\log_2|R|\rceil 次询问，其中 |L|,|R| 表示两个问题的可能解集大小。
这两个问题都是经典二分问题，使用二分恰好能做到上面给出的最小值。因此二分即为最优。

那么，如果记保证能猜对的最小猜测次数为 f(n)，显然有：

f(n)=1+\min\limits_{1\le a\le n}\{\max\{f(a-1),f(n-a),\lceil\log_2a\rceil+\lceil\log_2(n-a+1)\rceil\}\}

边界条件为 f(0)=f(1)=0。

在 init() 内如此暴力递推并记录转移位置即可获得 100 分。我没写这部分做法，不保证这句话正确

注：f(1500)=20。出题人卡的很死（无贬义或辱骂情绪）。

那么 101 分做法呢？

上面的递推很难优化，我们应该试图寻找最优转移位置的规律。记 n 的最小最优转移位置为 p(n)。

我写了一段打表 js：

f=[0,0];
p=[0,1];
for(n=2;n<=99;++n)
{
    f.push(n);p.push(1);
    for(i=1;i<=n;++i)
    {
        c=1+Math.max(Math.ceil(Math.log2(i))+Math.ceil(Math.log2(n-i+1)),f[i-1],f[n-i]);
        if(c<f[n]) f[n]=c,p[n]=i;
    }
}
console.log(p);

观察输出结果，规律实在太明显了：

[0, 1, 
 1, 
 1, 
 1, 2, 
 1, 2, 
 1, 2, 3, 4, 
 1, 2, 3, 4, 
 1, 2, 3, 4, 5, 6, 7, 8, 
 1, 2, 3, 4, 5, 6, 7, 8, 
 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 
 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 
 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 
 1, 2, 3, 4]

稍微提炼一下，规律可以表示为：对于 2^m\le n<2^{m+1}，p(n)=(n\bmod 2^{m-1})+1。

此规律可以和 Bonus 中提到的其他规律使用数学归纳法一起证明。细节由读者补充。

那么我们就有了 O(\log n) 计算 p(n) 的方法，时间复杂度 O(T\log^2n)，显然不会超时。实测可以拿到 101 分。

也可以把 p(n) 搬到 init() 内进行线性预处理，时间复杂度 O(n+T\log n)。我没写这部分做法，不保证这句话正确

参考实现：

#include <utility>//因为这个 CE 了一次
int Query(int);//因为这个 CE 了第二次
inline int getGuessPosition(int len)//return in [0,len)
{
    int i=0;while(len>>i)++i;
    return len%(1<<(i-2));
}
inline std::pair<int,int> finalGuess(int l,int mid,int r)
{
    int l0,r0,mid0;
    l0=l,r0=mid;
    while(r0>l0)
    {
        mid0=(l0+r0)>>1;
        if(Query(mid0)) l0=mid0+1;else r0=mid0;
    }
    int a=l0;
    l0=mid,r0=r;
    while(r0>l0)
    {
        mid0=(l0+r0)>>1;
        if(Query(mid0+1)) r0=mid0;else l0=mid0+1;
    }//这两个二分实际上可以写一起
    int b=l0;
    return std::make_pair(a,b);
}
std::pair<int,int> guess(int l,int r)
{
    if(l==r) return std::make_pair(l,r);
    int pos=l+getGuessPosition(r-l+1);
    int ret=Query(pos);
    if(ret==-1) return guess(pos+1,r);
    if(ret==0) return finalGuess(l,pos,r);
    return guess(l,pos-1);//一开始 1 和 -1 应该执行的操作写反了一次
}
std::pair<int,int> Guess(int n,int c)
{
    return guess(1,n);
}
void init(){}

Bonus：f(n) 的表达式

用上面那段程序计算 f(n)，规律也很明显：

[0, 0, 
 2,
 3,
 4, 4,
 5, 5,
 6, 6, 6, 6,
 7, 7, 7, 7,
 8, 8, 8, 8, 8, 8, 8, 8,
 9, 9, 9, 9, 9, 9, 9, 9,
 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
 13, 13, 13, 13]

也就是：对于 2^m\le n<2^{m+1}，f(n)=2m+[n\ge3\cdot2^{m-1}]。

容易发现 m+[n\ge3\cdot2^{m-1}] 可以表示为 \lfloor\log_2\frac{4n}3\rfloor，因此 f(n)=\lfloor\log_2n\rfloor+\lfloor\log_2\frac{4n}3\rfloor，与题目中的表达式一致。出题人你卡的真死（无贬义或辱骂情绪）。

Bonus Bonus：所有最优转移位置

上面我们只计算了最小最优转移位置，那么所有最优转移位置是个什么情况呢？

我们用 P(n) 代表 n 的所有最优转移位置构成的集合。

仍然使用上面那段程序，计算结果我使用 Excel 可视化了一下：

标灰代表此位置不存在，标黑代表这是最优转移位置，标白代表这不是最优转移位置。

稍微提炼一下：对于2^m\le n<2^{m+1}，1\le i\le n，i\in P(n) 当且仅当 (i-1)\bmod 2^{m-1}\ge n\bmod 2^{m-1}。

结论和图片都很美。

P.S. 可以算出（图形无穷大时）S=\dfrac{5}{24}a^2，a 为底边长。

P8111 [Cnoi2021]区间 题解

P8111 [Cnoi2021]区间题解