题解：UOJ111 & P3645 [APIO2015] Jakarta Skyscrapers

chu_yh · 2025-07-03 16:36:01 · 题解

题解区大部分代码无法通过数据更强的UOJ111【APIO2015】Jakarta Skyscrapers，建议阅读我的，自认为写的最好的一集。建议提交前往 UOJ111。如果写得好，就点个赞吧。

水题。题面不难理解，我们直接进入正题。

解题思路

发现神秘生物反复横跳（~~好像跳蚤~~）会产生多个状态，定义一个三元组 (\mathrm{pos},x,\mathrm{step}) 表示 doge 的状态：信息用了 \mathrm{step} 步到位于大楼 \mathrm{pos} 的跳跃能力（之后简称弹力）为 x 的 doge 那里。

先别着急 DP，发现状态的转移分为两种：

同一栋楼里的 doge 传递信息，步数不变。
一只 doge 跳到其他楼里，步数加一。

发现越往后转移，步数只有可能更大。联想到图的遍历，每个状态类比为图上的节点。同样，离初始节点（也就是初始状态）越远的节点所需的步数越多，于是，我们就能用一种类似与 BFS 的方法，先把离初始节点近的点处理了，再去处理远的，保证了答案的正确性。

具体实现

因为同一楼内信息可无代价传递给楼内的所有 doge，我们再定义一个二元组 (\mathrm{pos},\mathrm{step}) 表示信息用了 \mathrm{step} 步到了大楼 \mathrm{pos}，称为楼 \mathrm{pos} 的状态。楼的状态其实包含了目前在楼内的所有 doge 的状态，下文所说把某栋楼的状态压入队，其实就是把目前在楼内的所有 doge 的状态压入队。

具体的，用个 vector 储存每栋楼里 doge 的弹力。先让起始状态 (s,0)（s 为 0 号 doge 所在楼的编号）入队。开始广度优先遍历。注意，队列中的是 doge 的状态！

取出队首状态 (\mathrm{pos},x,\mathrm{step})；
判断其下一步能否到达 t（即 1 号 doge 所在楼）。如果能，找到答案，结束程序。
分别向左右跳（向左右转移状态），注意判断是否出界。

重复上述过程即可。

时间复杂度证明

利用根号分治思想。每只弹跳力为 p 的 doge 可延伸出的状态数只有 \sqrt n 种，共 n 只 doge，时间复杂度 O(n \sqrt n)。

代码实现

节省内存小技巧

由上面的具体实现可知，我们需要把 doge 的状态和楼的状态分别建判重数组。楼的状态很好开，只需给总共 n(n\le30000) 栋楼开就好了（不需要管步数）。但 doge 的状态就难办了：要开 n^2 的 bool 型数组。

考虑使用 bitset。可以将 bitset 理解为 bool 型数组。但 bitset 每个元素仅占 1 比特，N 位仅占用 N \over 8 字节。

使用范例：

#include<bitset> //头文件准备
#include<iostream>
bitset<100> b;// -> bool b[100];

int main(){
    for(int i=0;i<100;i++) std::cin>>b[1];
    b[6]=true;
    for(int i=0;i<100;i++) if(b[i]) std::cout<<b[i]<<std::endl;
    return 0;
}

把 doge 的状态压入队：`Push` 函数

struct doge{int pos,x,step;};//队列状态:用了step步到有跳跃能力为x的doge的大楼pos
queue<doge> q;//BFS

void Push(doge u){
    if(!b[u.pos][u.x])//判断该状态是否已进入过队
        b[u.pos][u.x]=1,q.push(u);
}

把楼 pos 的状态压入队并标记：`mark` 函数

void mark(int pos,int step){//把楼pos的状态压入队并标记
    vis[pos]=true;//别忘了打标记
    for(int P:p[pos]) Push((doge){pos,P,step});//把目前在楼内的所有doge的状态压入队
}

状态的转移：`turn` 函数

void turn(register doge u,register bool F=0){//转移状态
    u.step++,u.pos+=F?u.x:-u.x;
    Push(u);//别忘了自己入队
    if(!vis[u.pos]) mark(u.pos,u.step);
}

Code

自认为本代码是题解区可读性最高的了。本代码需要吸氧（其实能过 UOJ111 的都要吸氧），有兴趣的话可以尝试卡常。

#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
using namespace std;
inline int read(){
    register int X=0;register bool F=0;register char C=getchar();
    while(C<'0'||'9'<C){F=0;if(C=='-') F=1;C=getchar();}
    while('0'<=C&&C<='9'){X=(X<<3)+(X<<1)+(C^'0');C=getchar();}
    return F?-X:X;
}
const int N=3e4+2;
int n,m,s,t;
vector<int> p[N];//p[i]表示楼i上的doge的弹力p的集合
bitset<N> b[N];//bitset节省内存,就是省内存的bool b[N][N]
//状态判重,b[pos][x]表示"弹力为x的doge到大楼pos"的状态是否出现过
struct doge{int pos,x,step;};
//队列状态:用了step步到有跳跃能力为x的doge的大楼pos
queue<doge> q;//BFS
bool vis[N];//vis[i] 标记大楼i是否到过

void Push(doge u){//doge的状态入队
    if(!b[u.pos][u.x]) b[u.pos][u.x]=1,q.push(u);
}

void mark(int pos,int step){//把楼pos的状态压入队并标记
    vis[pos]=true;
    for(int P:p[pos]) Push((doge){pos,P,step});
}

void turn(register doge u,register bool F=0){//转移状态
    u.step++,u.pos+=F?u.x:-u.x;
    Push(u);
    if(!vis[u.pos]) mark(u.pos,u.step);
}

int main(){
    n=read(),m=read();
    s=read();
    p[s].push_back(read());
    t=read();
    p[t].push_back(read());//留意读入顺序!!!
    if(s==t){putchar('0');return 0;}
    for(register int i=2,d;i<m;i++){
        d=read();
        p[d].push_back(read());
    }
    mark(s,0);//出发
    while(!q.empty()){
        doge u=q.front();
        q.pop();
        if(u.pos-u.x==t||u.pos+u.x==t){
            printf("%d",u.step+1);
            return 0;
        }
        if(u.pos-u.x>=0) turn(u);
        if(u.pos+u.x<n) turn(u,1);
    }
    putchar('-'),putchar('1');
    return 0;
}

从本题我们能学到什么

bitset 的省内存小技巧：代替开不下的 bool 型数组。
BFS 状态观：把广度优先遍历的对象像 DP 一样看作许多状态。
大小状态包含技巧：楼的大状态包含 doge 的小状态，带动理解，清晰思路。

完结撒花！感谢你的耐心。