专栏文章

题解：UOJ111 & P3645 [APIO2015] Jakarta Skyscrapers

cchu_yh
P3645题解参与者 2已保存评论 10

文章操作

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

当前评论
10 条
当前快照
1 份
快照标识符
@miozqfy5
此快照首次捕获于
2025/12/03 03:48
3 个月前
此快照最后确认于
2025/12/03 03:48
3 个月前
查看原文
题解区大部分代码无法通过数据更强的UOJ111【APIO2015】Jakarta Skyscrapers，建议阅读我的，自认为写的最好的一集。建议提交前往 UOJ111。如果写得好，就点个赞吧。
水题。题面不难理解，我们直接进入正题。

解题思路

发现神秘生物反复横跳（好像跳蚤）会产生多个状态，定义一个三元组 (pos,x,step)(\mathrm{pos},x,\mathrm{step}) 表示 doge 的状态：信息用了 step\mathrm{step} 步到位于大楼 pos\mathrm{pos} 的跳跃能力（之后简称弹力）为 xx 的 doge 那里。
先别着急 DP，发现状态的转移分为两种：
  • 同一栋楼里的 doge 传递信息，步数不变。
  • 一只 doge 跳到其他楼里，步数加一。
发现越往后转移，步数只有可能更大。联想到图的遍历，每个状态类比为图上的节点。同样，离初始节点（也就是初始状态）越远的节点所需的步数越多，于是，我们就能用一种类似与 BFS 的方法，先把离初始节点近的点处理了，再去处理远的，保证了答案的正确性。

具体实现

因为同一楼内信息可无代价传递给楼内的所有 doge，我们再定义一个二元组 (pos,step)(\mathrm{pos},\mathrm{step}) 表示信息用了 step\mathrm{step} 步到了大楼 pos\mathrm{pos}，称为楼 pos\mathrm{pos} 的状态。楼的状态其实包含了目前在楼内的所有 doge 的状态，下文所说把某栋楼的状态压入队，其实就是把目前在楼内的所有 doge 的状态压入队。
具体的，用个 vector 储存每栋楼里 doge 的弹力。先让起始状态 (s,0)(s,0)（ss 为 00 号 doge 所在楼的编号）入队。开始广度优先遍历。注意，队列中的是 doge 的状态！
  • 取出队首状态 (pos,x,step)(\mathrm{pos},x,\mathrm{step})；
  • 判断其下一步能否到达 tt（即 11 号 doge 所在楼）。如果能，找到答案，结束程序。
  • 分别向左右跳（向左右转移状态），注意判断是否出界。
重复上述过程即可。

时间复杂度证明

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

代码实现

节省内存小技巧

由上面的具体实现可知，我们需要把 doge 的状态和楼的状态分别建判重数组。楼的状态很好开，只需给总共 n(n≤30000)n(n\le30000) 栋楼开就好了（不需要管步数）。但 doge 的状态就难办了：要开 n2n^2 的 bool 型数组。
考虑使用 bitset。可以将 bitset 理解为 bool 型数组。但 bitset 每个元素仅占 11 比特，NN 位仅占用 N8N \over 8 字节。
使用范例：
CPP
#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 函数

CPP
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);
}

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

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

状态的转移：turn 函数

CPP
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 的都要吸氧），有兴趣的话可以尝试卡常。
CPP
#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;
}

从本题我们能学到什么

  1. bitset 的省内存小技巧：代替开不下的 bool 型数组。
  2. BFS 状态观：把广度优先遍历的对象像 DP 一样看作许多状态。
  3. 大小状态包含技巧：楼的大状态包含 doge 的小状态，带动理解，清晰思路。
完结撒花！感谢你的耐心。

评论

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

正在加载评论...