专栏文章

题解：P14134 【MX-X22-T5】「TPOI-4E」Get MiN? Get MeX!

CCuteLord
P14134题解参与者 5已保存评论 4

文章操作

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

当前评论
4 条
当前快照
1 份
快照标识符
@minq10eb
此快照首次捕获于
2025/12/02 06:28
3 个月前
此快照最后确认于
2025/12/02 06:28
3 个月前
查看原文
简单题？

10pts

我们把 1∼n1\sim n 都扫一遍，其中会有两个值为 11 的位置，用 22 类询问判断一下就好了

25pts

首先我们不难发现，将一个序列从中间劈开，左右两边的 min+mexmin+mex 的值是相等的，所以我们考虑维护两个区间，每次将每个区间砍半，询问这 44 个区间，我们发现必然有两个区间的值相等，且这两个值必然是 44 区间的值中的最小值，同时 00 和 11 在这两个区间内，证明不难留给读者自行思考。那么每次就可以将区间大小缩小一半，询问次数为 O(4log⁡2n)O(4\log_2 n)。最后找出两个值为 11 的点后用 10pts 的方法判断就好了。

40pts

容易想到 44 个区间中有一个询问是没有必要的，询问次数为 O(3log⁡2n)O(3\log_2 n)

100pts

我们这个 log⁡n\log n 是降不下来的，于是考虑怎么每次用 22 次询问就可以缩小范围。假设当前的两个区间为 [l1,r1],[l2,r2][l_1,r_1],[l_2,r_2]，他们询问出的值为 xx，两个区间的中点为 m1,m2m_1,m_2，区间 [l1,m1],(m1,r1],[l2,m2],(m2,r2][l_1,m_1],(m_1,r_1],[l_2,m_2],(m_2,r_2] 询问出的值为 a,b,c,da,b,c,d， y=min⁡(a,b,c,d)y=\min(a,b,c,d)，那么 y≤xy\le x。
同时我们有当 a=ba=b 或 c=dc=d 时 y<xy<x,当 a=ca=c 或 a=da=d 或 b=cb=c 或 b=db=d 时 y=xy=x。
证明不难。
由于 a=ba=b 或者 c=dc=d 同理，所以我们只考虑 a=ba=b。
假设 00 在 [l1,m1][l_1,m_1] 区间内，那么 min⁡[l1,m1]=0\min[l_1,m_1]=0 且 mex⁡[l1,m1]=a\operatorname{mex}[l_1,m_1]=a，此时由于 a=ba=b 所以 min⁡(m1,r1]=a\min (m_1,r_1]=a 且 mex⁡(m1,r1]=0\operatorname{mex}(m_1,r_1]=0。
我们发现，此时在区间 [l1,r1][l_1,r_1] 内 0∼a0 \sim a 都存在，那么 min⁡[l1,r1]=0\min[l_1,r_1]=0 且 mex⁡[l1,r1]=a+1\operatorname{mex}[l_1,r_1]=a+1，即 x=a+1x=a+1，也即 y<xy<x。
00 在 [l1,m1][l_1,m_1] 区间内同理。
由于 a=ca=c 或 a=da=d 或 b=cb=c 或 b=db=d 也同理，所以我们也只考虑 a=ca=c。同样，我们假设 00 在区间 [l1,m1][l_1,m_1] 内，那么 min⁡[l1,m1]=0\min[l_1,m_1]=0 且 mex⁡[l1,m1]=a\operatorname{mex}[l_1,m_1]=a，此时由于 a=ca=c 所以 min⁡[l2,m2]=a\min[l_2,m_2]=a 且 mex⁡[l2,m2]=0\operatorname{mex}[l_2,m_2]=0。
我们知道，因为 min⁡[l2,m2]=a\min[l_2,m_2]=a，所以 aa 一定在 [l2,m2][l_2,m_2] 中，那么 aa 就一定不在 (m1,r1](m_1,r_1] 中，因此 mex⁡[l1,r1]\operatorname{mex}[l_1,r_1] 一定等于 aa，同时根据 25pts 中的结论可以得到 min⁡[l2,r2]=a\min[l_2,r_2]=a，此时 x=ax=a，即 x=yx=y。
00 在 [l2,m2][l_2,m_2] 区间内同理。
现在我们考虑询问出 a,da,d，那么有一下几种情况：
  1. a=da=d：这个直接选 a,da,d；
  2. a>x,d>xa>x,d>x：直接选 b,cb,c；
  3. a=x,d>xa=x,d>x：选择 a,ca,c；
  4. a>x,d=xa>x,d=x：同理，选择 b,db,d；
  5. a<xa<x：选择 a,ba,b；
  6. d<xd<x：同理，选择 c,dc,d；
  7. a<x,d<xa<x,d<x：可以证明这种情况不存在。
由于区间每次会缩小一半，所以最多会缩小 log⁡n\log n 次，同时每次缩小使用 22 次询问，加上开始时询问的一次，总共 2log⁡2n+12 \log_2 n+1 次，在 n≤105n \le 10^5 时最多为 3535 次。
最后当区间缩小为两个点时，两个点必然一个为 11 一个为 00，直接用 10pts 的方法判断一下就做完了。
C
//by CuteLord uid:1114894
#include<bits/stdc++.h>
using namespace std;
int n;
int query(int l,int r,int op=0){
    /*
    询问就不给了
    */
}
int l1,r1;
int l2,r2;
int main(){
    cin>>n;
    l1=1,r1=n+1>>1;
    l2=r1+1,r2=n;
    int last=query(l1,r1);
    while(1){
        int m1=l1+r1>>1,m2=l2+r2>>1;
        int a=query(l1,m1);
        int b=query(m2+1,r2);
        if(a==b){
            r1=m1;
            l2=m2+1;
            last=a;
        }else if(a>last&&b>last){
            l1=m1+1;
            r2=m2;
        }else if(a<last){
            l2=m1+1,r2=r1;
            r1=m1;
            last=a;
        }else if(b<last){
            l1=l2,r1=m2;
            l2=m2+1;
            last=b;
        }else if(a==last&&b>last){
            r1=m1;
            r2=m2;
        }else if(b==last&&a>last){
            l1=m1+1;
            l2=m2+1;
        }
        if(l1==r1&&l2==r2)break;
        else if(l1==r1){
            m2=l2+r2>>1;
            a=query(l2,m2);
            b=query(m2+1,r2);
            if(a<b)r2=m2;
            else l2=m2+1;
            break;
        }else if(l2==r2){
            m1=l1+r1>>1;
            a=query(l1,m1);
            b=query(m1+1,r1);
            if(a<b)r1=m1;
            else l1=m1+1;
            break;
        }
    }
    if(query(l1,l1,1)<0)cout<<"! "<<l1;
    else cout<<"! "<<l2;

}

评论

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

正在加载评论...