03-23 21:29 华中科技大学算法工程师发布于湖北

关注

第36次CCF CSP认证 T4 题解

A.题目大意

有 $n$ 个格子，每个格子上的数构成一个序列 $\{{a_n}\}$ ,其中 $a_i$ 满足 $a_i<i$ 且 $a_n=0$ 。从第一块格子出发，每次可以落到第 $i+1$ 个格子和第 $min(n,i+k_i)$ 个格子中任意一个格子上面。但与此同时，落到了第 $i$ 个格子后，又得移动到第 $i-a_i$ 个格子上。求跳跃到第 $n$ 个格子的最小次数。数据规模如下： $1 \leq n \leq 10^5,0 \leq a_i < i , 1 \leq k_i \leq 10^9$ .

B.思路

我们定义一次完整的行动为：从 $i$ 跳到 $j(i+1 \leq j \leq min(n,i+k_i))$ ,然后退到 $j-a_j$ 的位置。

设 $dp[i]$ 为从第 $i$ 个格子跳到第 $n$ 个格子需要的最少跳跃次数，则我们容易写出状态转移方程为：

$dp[i]=1+min\{dp[j-a_j],i+1 \leq j \leq min(n,i+k_i)\}$ ，边界条件是 $dp[n]=0$ 。

如果采用暴力的方法，对每个 $dp[i]$ 都这么计算一次，时间复杂度会来到 $O(n^2)$ ,对于题目所给的数据规模是必然会超时的。下面我们考虑如何优化算法。

这里我们采用反向BFS的思路：之前我们考虑的是由某个点出发，最终能到达哪些点。现在考虑的是从到达的点反推，看哪些点是出发点。我们有：如果 $j-a_j=x$ ， $j$ 是从某个点跳跃后但是回退前的位置，则满足 $i+1 \leq j \leq i+k_i$ 的所有点 $i$ 都能通过一次完整的行动到达 $x$ ,稍加变形可得 $i$ 满足的条件为 $i\leq j-1且i+k_i \geq j$ 。 $x=j-a_j$ 可以预处理，预先记录所有满足此的 $j$ (邻接表 $rev[x]$ )。当后续BFS过程中遍历到 $x$ 时，我们遍历 $rev[x]$ 里的每个 $j$ ，再通过 $j$ 找到满足前面推到出的条件的且未被访问的 $i$ ，设置 $dist[i] = dist[x]+1$ ,并且将其入队。

接下来，我们需要完成以下操作:

1.在区间 $[1,j-1]$ 中查找所有满足 $i+k_i \geq j$ 且未被访问的 $i$ ,将访问过的 $i$ 设置为已访问状态。对于每个位置 $i$ ,我们需要维护 $right[i]=min(n,i+k_i)$ 。

2.查询区间 $[1,j-1]$ 的最大值和它的位置，如果最大值 $\geq j$ ，那么说明存在点 $i$ 满足 $i+k_i\geq j$ ,取出该点，记为 $pos$ 。

3.将 $dp[pos]$ 设为当前层数 $+1$ ,入队，并把pos的值改为 $-\infty$ ,来表示访问过的状态

4.重复2，3过程，直到区间最大值 $<j$ 。

综合上面需要的操作，可以采用线段树来完成，取出和查询都是 $O(logn)$ 的复杂度，每个点被取出1次，总复杂度为 $O(nlogn)$

C.具体操作

1.设置 $to[i]=i-a_i$ ,然后有 $rev[to[i]]=i$ 。

2.初始化线段树

3.标记访问

4.BFS(重点)

D.Code

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include<queue>
const int N = 1e5 + 10;
const int INF = 1e9;
const int N_INF = -1e9;
int n, a[N], k[N], to[N];
vector<int> rev[N];
int dist[N];

struct SegTree
{
    int maxv[N << 2], pos[N << 2];
    void build(int id, int l, int r)
    {
        if (l == r)
        {
            maxv[id] = min(n, k[l] + l);
            pos[id] = l;
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 + 1, mid + 1, r);
        if (maxv[id << 1] >= maxv[id << 1 + 1])
        {
            maxv[id] = maxv[id << 1];
            pos[id] = pos[id << 1];
        }
        else
        {
            maxv[id] = maxv[id << 1 + 1];
            pos[id] = pos[id << 1 + 1];
        }
    }
    void update(int id, int l, int r, int p, int val)
    {
        if (l == r)
        {
            maxv[id] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid)
            update(id << 1, l, mid, p, val);
        else
            update(id << 1 + 1, mid + 1, r, p, val);
        if (maxv[id << 1] >= maxv[id << 1 + 1])
        {
            maxv[id] = maxv[id << 1];
            pos[id] = pos[id << 1];
        }
        else
        {
            maxv[id] = maxv[id << 1 + 1];
            pos[id] = pos[id << 1 + 1];
        }
    }
    pair<int, int> query(int id, int l, int r, int ql, int qr)
    {
        if (ql <= l && r <= qr)
            return {maxv[id], pos[id]};
        int mid = (l + r) >> 1;
        if (qr <= mid)
            return query(id << 1, l, mid, ql, qr);
        if (ql >= mid + 1)
            return query(id << 1 + 1, mid + 1, r, ql, qr);
        auto left = query(id << 1, l, mid, ql, qr);
        auto right = query(id << 1 | 1, mid + 1, r, ql, qr);
        if (left.first >= right.first)
            return left;
        else
            return right;
    }
}seg;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int j=1;j<=n;j++)
    cin>>k[j];
    for(int i=1;i<=n;i++)
    {
        to[i] = i - a[i];
        rev[to[i]].push_back(i);
    }
    seg.build(1,1,n);
    seg.update(1,1,n,n,N_INF); //将n标记为visited
    memset(dist,-1,sizeof(dist)); //初始化
    dist[n] = 0;
    queue<int> q;
    q.push(n);
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        for(auto j: rev[x])
        {
            int lim = min(n,j-1);
            if(lim<1) continue;
            while(1)
            {
                auto [mx,pos] = seg.query(1,1,n,1,lim);
                if(mx < j) break;
                dist[pos] = dist[x] + 1;
                q.push(pos);
                seg.update(1,1,n,pos,N_INF);
            }
        }
    }
    cout<<dist[1];
    return 0;
}