专栏文章

题解：P9292 [ROI 2018] Robomarathon

lltl0825
P9292题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mingzl90
此快照首次捕获于
2025/12/02 02:15
3 个月前
此快照最后确认于
2025/12/02 02:15
3 个月前
查看原文
题目传送门
更好的阅读体验

题目大意：

有 NN 名机器人选手参加马拉松，选手编号为 1…N1 \dots N，分道编号也为 1…N1 \dots N。选手 ii 占据分道 ii，跑完全程需要 aia_i 秒。
  • 设 S⊆{1,2,…,N}S \subseteq \{1, 2, \dots, N\} 表示初始发炮的分道集合。
  • 选手 ii 的起跑时刻为： xi=min⁡j∈S∣i−j∣x_i = \min_{j \in S} |i - j|
  • 选手 ii 的冲线时间为： fi=ai+xif_i = a_i + x_i
  • ii 的排名即为满足 fj<fif_j<f_i 的 jj 的个数 +1+1。
当 p=1p=1 时：对于每个选手 ii，求它的最好排名（最小）
当 p=2p=2 时：对于每个选手 ii，求它的最坏排名（最大）

题目思路：

  1. p=1p=1
    对于 p=1p=1 很好考虑：直接在当前位置放一个，别的地方都不放，这对于当前的 ii 是最优的。
    对于 ii 来说，排名在其前的满足 aj+∣i−j∣<aia_j+ \left |i-j \right | < a_i。
    当 j<ij<i 时：aj+i−j<aia_j+i-j<a_i 即 aj−j<ai−ia_j-j<a_i-i。我们将 ai−ia_i-i 当作一个数丢入树状数组，每次从左到右扫一遍，对于当前的就查询 ai−i−1a_i-i-1 的前缀。
    当 j>ij>i 时：aj−i+j<aia_j-i+j<a_i 即 aj+j<ai+ia_j+j<a_i+i。我们将 ai+ia_i+i 当作一个数丢入树状数组，每次从右到左扫一遍，对于当前的就查询 ai+i−1a_i+i-1 的前缀。
    将两次操作的和 +1+1 输出即可。
  2. p=2p=2
    我们考虑先将所有跑道放上喇叭。 假设 i≤⌊n2⌋i \le \left \lfloor \frac{n}{2} \right \rfloor 。
    对于当前位置 ii，我删去它的喇叭肯定会使 ii 的排名不增，那我肯定删去它。
    若我同时在删去 i+1i+1 和 i−1i-1。那么 ii 的 xi=2x_i =2，i−1i-1 和 i+1i+1 的 xi=1x_i=1 别的 xix_i 都是 00，肯定会使 ii 的排名不增，那我肯定删去它。
    重复这个流程，知道左边剩下一个 11 右边是 2×i−1∼n2\times i -1 \sim n，这时不能再这样了，因为 11 删了就会导致 1∼i−11\sim i-1 的发令喇叭变成 2×i−12\times i-1 不优。
    当然，我们还可以只放在 nn 这个位置，这也是优的。
    所以，有两种：一种是放在 11 和 2×i−1∼n2\times i -1 \sim n 另一种是放在 nn。
    对于右半部分，即 i>⌊n2⌋i>\left \lfloor \frac{n}{2} \right \rfloor 同理，可以自己试着推一下。\

代码 （详细注释，细节提醒）

CPP
#include<bits/stdc++.h>
#define int long long
#define OUT(x) cout<<"LINE: "<<__LINE__<<" INFO: "<<x<<'\n';
using namespace std;
int n,p;
int a[400010];
int tree[1600010];
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int v)
{
    for(;x<=800000;x+=lowbit(x))
    {
        tree[x]+=v;
    }
}
int ask(int x)
{
    int ans=0;
    for(;x;x-=lowbit(x))
    {
        ans+=tree[x];
    }
    return ans;
}
int b[400010];
int c[400010];//ai+i
int d[400010];//ai-i
int ans[400010];
int ans1[400010];
struct node{
    int pos,val,op,q,add;
}kk[850010];
int e[800010];
int f[400010];
int g[400010];
void solve(int op)
{
    if(op == 0)
    {
        int k=n/2;
        memset(tree,0,sizeof(tree));
        /*
		[1,i-1]的统计：满足fj<fi的j的数量 
		a[j]+i-j<a[i]
		a[j]-j<a[i]-i
		*/
        for(int i=1;i<=k;i++) 
        {
            ans1[i]+=ask(c[i]-1);
            add(c[i],1);
        }
        memset(tree,0,sizeof(tree));
        int ll=0;
        /*
        这里是统计[i,2*i-1]：满足fj<fi的j的数量  
        我们发现，对于一个 i+1<=j<=2*i-1
		它要满足：a[j]+2*i-1-j<=a[i]+i-1
		a[j]-j<=a[i]-i
		所以我们需要知道，在[i,2*i-1]这个区间中，满足a[j]-j<=a[i]-i的j的数量
		那么我们将每个i的这种询问拆成两个询问：[1,2*i-1]满足a[j]-j<=a[i]-i的j的数量-[1,i-1]满足a[j]-j<=a[i]-i的j的数量，类似前缀查询
		这样就可以把这些询问记下来，按坐标排序，依次查询。
		我们还要把每个点加入进去，也就也是在i位置加入a[i]-i
		node成员的意义：
		pos:查询或加入的时间。
		val：查询或加入的值
		op：查询对对应i的贡献（i-1是-1，2*i-1是1，这样加一下就可以达到区间查询）
		q：查询对应哪个i
		add：当前是加入还是查询 
		*/ 
        for(int i=k;i>=1;i--) 
        {
            kk[++ll]={i-1,d[i]-1,-1,i,0};//拆询问 
            kk[++ll]={2*i-1,d[i]-1,1,i,0};
        }
        for(int i=1;i<=2*k-1;i++)
        {
            kk[++ll]={i,d[i],1,1,1};//每个点要加入 
        }
        sort(kk+1,kk+ll+1,[](node x,node y){return x.pos==y.pos?x.add>y.add:x.pos<y.pos;});//排序，注意，当时间相同时，这里是先加入，在查询 
        for(int i=1;i<=ll;i++)
        {
            if(kk[i].add)//加入 
            {
                add(kk[i].val,1);
                continue;
            }
            ans1[kk[i].q]+=kk[i].op*ask(kk[i].val);//查询 
        }
        /*
        [2*i,n]：满足fj<fi的j的数量  
        j要满足：f[j]<f[i]+i-1
		所以要将a[i]与a[i]+i-1离散化 
        这里需要小心一些（细节多）。
        我们从 floor(n/2) ~ 1枚举 
		当i%2 == 0时：我们每次加入a[i*2]和a[i*2+1]，其中i=n/2时只能加入a[i*2]
		当i%2 != 0时：我们每次加入a[i*2]和a[i*2+1]
		每次查询a[i]+i-1的前缀 
		*/
        ll=0;
        memset(tree,0,sizeof(tree));
        int len1=0;
        //离散化 
        for(int i=1;i<=n;i++)
        {
            e[++len1]=a[i];
            e[++len1]=a[i]+i-1;
        }
        sort(e+1,e+1+len1);
        len1=unique(e+1,e+1+len1)-e-1;
        for(int i=1;i<=n;i++)
        {
            f[i]=lower_bound(e+1,e+1+len1,a[i])-e;
            g[i]=lower_bound(e+1,e+1+len1,a[i]+i-1)-e;
        }
        if(k*2 == n)//进行操作 
        {
            for(int i=k;i>=1;i--)
            {
                if(i == k)
                {
                    add(f[i*2],1);   
                }
                else
                {
                    add(f[i*2],1);
                    add(f[i*2+1],1);
                }
                ans1[i]+=ask(g[i]-1);
            }
        }
        else
        {
            for(int i=k;i>=1;i--)
            {
                add(f[i*2],1);
                add(f[i*2+1],1);
                ans1[i]+=ask(g[i]-1);
            }
        }
    }
    else//右边同理，我就不说了 
    {
        int k=n/2+1;
        memset(tree,0,sizeof(tree));
        for(int i=n;i>=k;i--)
        {
            ans1[i]+=ask(d[i]-1);
            add(d[i],1);
        }
        memset(tree,0,sizeof(tree));
        int ll=0;
        for(int i=k*2-n;i<=n;i++)
        {
            kk[++ll]={i,c[i],1,1,1};
        }
        for(int i=k;i<=n;i++)
        {
            kk[++ll]={2*i-n-1,c[i]-1,-1,i,0};
            kk[++ll]={i,c[i]-1,1,i,0};
        }
        sort(kk+1,kk+ll+1,[](node x,node y){return x.pos==y.pos?x.add>y.add:x.pos<y.pos;});
        for(int i=1;i<=ll;i++)
        {
            if(kk[i].add)
            {
                add(kk[i].val,1);
                continue;
            }
            ans1[kk[i].q]+=kk[i].op*ask(kk[i].val);
        }
        ll=0;
        memset(tree,0,sizeof(tree));
        int len1=0;
        for(int i=1;i<=n;i++)
        {
            e[++len1]=a[i];
            e[++len1]=a[i]+n-i;
        }
        sort(e+1,e+1+len1);
        len1=unique(e+1,e+1+len1)-e-1;
        for(int i=1;i<=n;i++)
        {
            f[i]=lower_bound(e+1,e+1+len1,a[i])-e;
            g[i]=lower_bound(e+1,e+1+len1,a[i]+n-i)-e;
        }
        if(k*2-n-1 == 1)
        {
            for(int i=k;i<=n;i++)
            {
                if(i == k)
                {
                    add(f[2*i-n-1],1);   
                }
                else
                {
                    add(f[i*2-n-1],1);
                    add(f[i*2-n-2],1);
                }
                ans1[i]+=ask(g[i]-1);
            }
        }
        else
        {
            for(int i=k;i<=n;i++)
            {
                if(i == k)
                {
                    continue;
                }
                add(f[i*2-n-1],1);
                add(f[i*2-n-2],1);
                ans1[i]+=ask(g[i]-1);
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>p;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i]+i;
    }
    //离散化 
    sort(b+1,b+1+n);
    int len=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++)
    {
        c[i]=lower_bound(b+1,b+1+len,a[i]+i)-b;
    }
    for(int i=1;i<=n;i++)
    {
        b[i]=a[i]-i;
    }
    sort(b+1,b+1+n);
    len=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++)
    {
        d[i]=lower_bound(b+1,b+1+len,a[i]-i)-b;
    }
    if(p == 1)
    {
        for(int i=n;i>=1;i--)//右->左 
        {
            ans[i]=ask(c[i]-1);
            add(c[i],1);
        }
        memset(tree,0,sizeof(tree));
        for(int i=1;i<=n;i++)//左->右 
        {
            ans[i]+=ask(d[i]-1);
            add(d[i],1);
        }
        for(int i=1;i<=n;i++)
        {
            cout<<ans[i]+1<<'\n';//不要忘了+1 
        }
        //a[j]+i-j<a[i] -> a[j]-j<a[i]-i
        //a[j]+j-i<a[i] -> a[j]+j<a[i]+i
    }
    if(p == 2)
    {
        for(int i=1;i<=n;i++)//左半部分，放在n的位置 
        {
            add(d[i],1);
        }
        for(int i=1;i<=n/2;i++)
        {
            ans[i]=ask(d[i]-1);
        }
        memset(tree,0,sizeof(tree));
        for(int i=1;i<=n;i++)//右半部分，放在1的位置 
        {
            add(c[i],1);
        }
        for(int i=n/2+1;i<=n;i++)
        {
            ans[i]=ask(c[i]-1);
        }
        solve(0);//左半部分 
        solve(1);//右半部分 
        for(int i=1;i<=n;i++)
        {
            cout<<max(ans[i],ans1[i])+1<<'\n';//不要忘了+1，取的是max 
        }
    }
    return 0;
}

评论

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

正在加载评论...