题解：P11554 [ROIR 2016] 假期旅行 (Day 1)

· · 题解

题目复述

Vasya 的出行路线中有 n 个车站和 q 个出行计划，其中有 m 张票已经被占用。对于每个出行计划，需要求出至少买多少张票才能完成这次旅行。

题目分析

通过观察题意，我们可以发现每一段旅行坐哪个空位其实与答案毫无关系，我们只需要关心需要坐几个不同的座位（也就是有几次需要因为位置被人占住而不得不换座）。
于是，我们就可以完全忽略座位编号，只是通过有人坐的间推理出无人的区间，然后将每个有空位的区间处理成一个区间（具象化表示为一条线段），同时将询问的区间也转化成线段，示意图如下（绘图技术较差，请包涵）： 由此，我们就将问题转化成了一个格式化、较为易懂的形式：用最少的区间，覆盖一个给定的区间。
对于这个问题，如果是单次询问，可以直接暴力求解拿下 63 分。
在此基础上，我们开始考虑在多次询问时该如何把时间复杂度控制在可以接受的范围内。
为了降低多次查询的总复杂度，我们可以通过倍增的方式降低单词查询的时间复杂度，具体表现为预处理一个数组，用 p(i,j) 表示在第 i 个车站上车，坐了 a^j 站后到达的车站。在此预处理数组的基础上进行倍增求解即可。

蒟蒻的 AC 代码

#include <bits/stdc++.h>
#define int long long
#define made_by return
#define Lhm 0
using namespace std;
const int N=2e5+5;
int n,m,k;
int num;
int pre_opt[N][30];//用倍增方法求出预处理数组 
vector<pair<int,int> >p[N];//记录题目给定的有人区间 
int read(){//试图卡常 
    int x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9'){
        if(ch=='-'){
            w=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
  return x*w;
}
int query(int s,int e){//倍增处理查找命令 
    int ans=0;
    for(int i=25;~i;i--){
        if(pre_opt[s][i]<e){
            ans+=pow(2,i);
            s=pre_opt[s][i];
        }
    }
    if(pre_opt[s][0]>=e){
        ans++;
    }
    else{
        ans=-1;//完成不了就返回 -1 
    } 
    return ans;
}
signed main(){
    n=read();
    m=read();
    k=read();
    for(int i=1;i<=m;i++){
        int l,r,idx;
        l=read();
        r=read();
        idx=read();
        p[idx].push_back(make_pair(l,r));
    }
    for(int i=1;i<=k;i++){//将有人的区间推理转化成无人的区间，方便后续处理 
        sort(p[i].begin(),p[i].end());
        int x=1;
        for(auto it:p[i]){
            if(it.first>x){
                pre_opt[x][0]=max(pre_opt[x][0],it.first);
            }
            x=it.second;
        }
        if(x<=n){
            pre_opt[x][0]=n;
        }
    }
    for(int i=1;i<=n;i++){
        pre_opt[i][0]=max(pre_opt[i][0],pre_opt[i-1][0]);
    }
    for(int j=1;j<=25;j++){//倍增求预处理数组 
        for(int i=1;i<=n;i++){
            pre_opt[i][j]=pre_opt[pre_opt[i][j-1]][j-1]; 
        }
    }
    int q;
    cin>>q;
    int st,en;
    for(int i=1;i<=q;i++){
        st=read();
        en=read();
        int r=query(st,en);
        cout<<r<<"\n";
    }
    made_by Lhm;
}

说在后面：蒟蒻的第一篇题解，求通过。