P10445「MYOI-R3」签到官方题解

zhuweiqi · 2024-02-13 23:49:31 · 题解

如果我们将签到点按其坐标从小到大排序，容易发现，对于第 i 个签到点来说，设其是路径上经过的最左边的签到点，如果此路径上经过的最右边的签到点是第 j 个签到点，那么在排除原第 p 个签到点的奖励的干扰下，i 递增时 j 不减，因此考虑用双指针维护。当然也需要考虑原第 p 个签到点的影响。具体操作如下：

第一步，记录原签到点在排序后对应的位置，设原第 p 个签到点排序后对应为第 st 个签到点。

第二步，枚举第 i 个签到点（此处默认为排序后的新编号，下同）作为当前路径的最左端（可以证明这样枚举一定能找到最优解）：

如果 i\leq st，讨论能否在时间限制 +5 的情况下到达第 st 个签到点：

如果能，将时间限制 +5，跳转至第三步。
否则，讨论单单往返一次第 i 个签到点会不会超时，会超时直接跳过本轮循环，跳转至第三步。

否则，则说明时间限制无法 +5。特别地，注意当 i=st+1 时右指针 j 需要回退，因为第 st 个签到点给的奖励突然消失了。

第三步，用双指针维护出当前情况下能到达的最右边的签到点，这点也需要按 x_i 和 x_j 的正负分类讨论，在此不过多赘述，详见代码。

第四步，得出当前这组答案 (i,j)，ans 及时更新，如果其是最优解之一则先记录下 i 这个左指针的位置。

第五步，当 i 枚举完时我们已经得到了各个最优解的左指针的位置，此时我们只需顺序枚举，找到第 i 个签到点在排序后对应的位置，用双指针或者二分筛去期望度不是最大的解，具体地：

如果使用二分，则二分查找第一个（即左指针坐标最小的）和最后一个（即左指针坐标最大的）包含此签到点的路径，将答案区间范围缩小（可以证明，答案区间范围一定连续）当然如果没有一条路径包含此签到点，就不能缩小答案区间范围。
但是我们能优化成双指针，因为答案区间范围中间不可能有空隙，假设原点左边有一组答案，则路径一定包含原点到其左指针的所有签到点，右边亦是如此，中间不可能有任何一条路径都不包含的签到点。

综上，总时间复杂度为 O(n\log n)，但是这个 O(n\log n) 的复杂度是常数小的 sort 快排贡献的，其余双指针相关操作的时间复杂度均为 O(n)，所以 n\leq 10^5 的子任务是给第一部分没用双指针的选手准备的，如果复杂度正确通过 n\leq 10^6 的子任务是绰绰有余的。

Std：（仅供参考）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
    ll n=0;
    int f=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0' && c<='9'){
        n=(n<<3)+(n<<1)+(c^48);
        c=getchar();
    }
    return n*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10^48);
    return;
}
struct node{
    ll x;
    int idx;
}s[1000002];
bool cmp(node a,node b){return a.x<b.x;}
vector<int> v;
int q[1000002];
int mat[1000002];
int e[1000002];
int main(){
    int n=read();
    ll m=read();
    int p=read();
    for(int i=1;i<=n;i++) s[i].x=read(),s[i].idx=i;
    sort(s+1,s+1+n,cmp);
    for(int i=1;i<=n;i++) mat[s[i].idx]=i;
    int st=mat[p];
    int ans=0;
    int j=1;
    for(int i=1;i<=n;i++){
        int f=0;
        if(i<=st){
            if(s[st].x<=0 && (-s[i].x<<1)<=m+5) f=5;
            if(s[i].x<=0 && 0<=s[st].x && (s[st].x-s[i].x<<1)<=m+5) f=5;
            if(0<=s[i].x && (s[st].x<<1)<=m+5) f=5;
        }
        if(i==st+1) j=i;
        if(f==0 && abs(s[i].x<<1)>m) continue;
        j=max(i,j);
        while(j<=n){
            if(s[j].x<=0) j++;
            else if(s[i].x<=0 && 0<=s[j].x && (s[j].x-s[i].x<<1)<=m+f) j++;
            else if(s[i].x>=0 && (s[j].x<<1)<=m+f) j++;
            else break;
        }
        j--;
        if(j-i+1==ans) v.push_back(i);
        if(j-i+1>ans){
            v.clear();
            ans=j-i+1;
            v.push_back(i);
        }
        j++;
    }
    int cnt=0;
    for(auto it:v) q[++cnt]=it;
    int l=1,r=cnt;
    for(int i=1;i<=n;i++){
        e[i]=mat[i];
        if(e[i]<q[l] || q[r]+ans-1<e[i]) continue;
        while(l<r && q[l]+ans-1<e[i]) l++;
        while(l<r && e[i]<q[r]) r--;
        if(l==r) break;
    }
    write(ans);
    putchar('\n');
    for(int i=q[l];i<=q[l]+ans-1;i++) write(s[i].idx),putchar(' ');
    return 0;
}

P10445「MYOI-R3」签到 官方题解

P10445「MYOI-R3」签到官方题解