HFOI 集训记录 20220915 - 测试订正

$\text{By DaiRuiChen007}$

题目来源：雀巢咖啡系列模拟赛 #28

I. 升降梯上

题目大意

开启了升降梯的动力之后，探险队员们进入了升降梯运行的那条竖直的隧道，映入眼帘的是一条直通塔顶的轨道、一辆停在轨道底部的电梯、和电梯内一杆控制电梯升降的巨大手柄

Nescafe 之塔一共有 $n$ 层，升降梯在每层都有一个停靠点。手柄有 $m$ 个控制槽，第 $i$ 个控制槽旁边标着一个数 $c_i$，满足 $-n<c_1<c_2<\cdots<c_m<n$，$c_i$ 表示手柄扳动到该槽时，如果 $c_i>0$，电梯将上升 $c_i$ 层；如果 $c_i<0$，表示手柄扳动到该槽时，电梯将下降 $-c_i$ 层；并且一定存在一个 $c_i=0$ 手柄最初就位于此槽中

注意升降梯只能在 $1\sim n$ 层间移动，因此扳动到使升降梯移动到 $1$ 层以下、$n$ 层以上的控制槽是不允许的

电梯每移动一层，需要花费 $2$ 秒钟时间，而手柄从一个控制槽扳到相邻的槽，需要花费 $1$ 秒钟时间，探险队员现在在 $1$ 层，并且想尽快到达 $n$ 层，他们想知道从 $1$ 层到 $n$ 层至少 需要多长时间？

数据范围保证 $n\le1000,m\le 20$

思路分析

把当前所在的位置 $pos$ 和当前手柄所在的控制槽 $opt$ 打包成一个状态 $(pos,opt)$，按题目要求连接边之后再图上跑一边 Dijkstra 即可

时间复杂度 $\Theta(nm^2\log nm)$

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1001,MAXM=21,INF=1e18;
struct node {
	int pos,opt,val;
};
struct status {
	int pos,opt,dis;
	inline friend bool operator <(const status &x,const status &y) {
		return x.dis>y.dis;
	}
};
vector <node> edge[MAXN][MAXM];
int dis[MAXN][MAXM],c[MAXM];
bool vis[MAXN][MAXM];
int n,m;
signed main() {
	int start=-1;
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;++i) {
		scanf("%lld",&c[i]);
		if(!c[i]) start=i;
	}
	for(int u=1;u<=n;++u) {
		for(int i=1;i<=m;++i) {
			for(int j=1;j<=m;++j) {
				int v=u+c[j];
				if(v<1||v>n) continue;
				edge[u][i].push_back((node){v,j,2*abs(c[j])+abs(i-j)});
			}
		}
	}
	memset(dis,0x3f,sizeof(dis));
	dis[1][start]=0;
	priority_queue <status> q;
	q.push((status){1,start,0});
	while(!q.empty()) {
		int pos=q.top().pos,opt=q.top().opt;
		q.pop();
		if(vis[pos][opt]) continue;
		vis[pos][opt]=true;
		for(auto e:edge[pos][opt]) {
			int _pos=e.pos,_opt=e.opt;
			if(dis[pos][opt]+e.val<dis[_pos][_opt]) {
				dis[_pos][_opt]=dis[pos][opt]+e.val;
				q.push((status){_pos,_opt,dis[_pos][_opt]});
			}
		}
	}
	int res=INF;
	for(int i=1;i<=m;++i) res=min(res,dis[n][i]);
	if(res==INF) puts("-1");
	else printf("%lld\n",res);
	return 0;
}

---

II. 塔顶试探

题目大意

探险队员们顺利乘坐升降梯来到了塔顶，塔顶有若干房间，房间之间连有通道，如果把房间看做节点，通道看做边的话，整个塔顶呈现一个有根树结构，并且每个房间的墙壁都涂有若干种颜色的一种

现在探险队员们在树根处，他们打算进一步了解塔顶的结构，为此，他们使用了一种特殊设计的机器人。这种机器人会从队员身边，也就是树根出发，之后对塔顶进行深度优先遍历，机器人每进入一个房间（无论是第一次进入还是返回），都会记录这个房间的颜色。最后，机器人会回到树根。显然，机器人会访问每个房间至少一次，并且穿越每条通道恰好两次（两个方向各一次），然后，机器人会得到一个颜色序列 $S$

但是，探险队员发现这个颜色序列并不能唯一确定塔顶的结构，现在他们想请你帮助他们计算，对于一个给定的颜色序列，有多少种可能的结构会得到这个序列，由于结果可能会非常大，你只需要输出答案对 $10^9$ 取模之后的值

数据范围保证：$|S|\le 300$

思路分析

考虑区间 dp，设 $dp_{l,r}$ 为区间 $[l,r]$ 的答案，显然 $dp_{l,r}\neq 0$ 的必要不充分的条件是 $S_l=S_r$

我们可以考虑枚举 $[l,r]$ 中的第一颗子树，其搜索完成返回的时候回到的位置 $S_k$，显然 $S_l=S_k$，此时这一部分的的答案应该是 $dp_{l+1,k-1}$，那么剩下的若干棵子树，可以继续看成以当前节点为根的一个子问题，我们可以得到这一部分的方法数是 $dp_{k,r}$，总的方法数是两个相乘

状态转移方程如下：

$$dp_{l,r}= \begin{cases} 0 &l>r\\ 1 &S_l=S_r\\ \sum\limits_{k=l+1}^{r-1} [S_k=S_l]\times dp_{l+1,k-1}\times dp_{k,r} &\text{otherwise} \end{cases}$$

时间复杂度 $\Theta(n^3)$

思路分析

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=601,MOD=1e9;
int dp[MAXN][MAXN];
char euler[MAXN];
signed main() {
	scanf("%s",euler+1);
	int n=strlen(euler+1);
	for(int i=1;i<=n;++i) dp[i][i]=1;
	for(int len=1;len<n;++len) {
		for(int l=1,r=l+len;r<=n;++l,++r) {
			if(euler[l]!=euler[r]) continue;
			dp[l][r]=dp[l+1][r-1];
			for(int k=l+1;k<=r-1;++k) {
				if(euler[l]!=euler[k]) continue;
				dp[l][r]=(dp[l][r]+dp[l+1][k-1]*dp[k][r]%MOD)%MOD;
			}
		}
	}
	printf("%lld\n",dp[1][n]);
	return 0;
}

---

III. 礼物运送

题目大意

机器人刚刚探查归来，探险队员们突然发现自己的脚下出现了一朵朵白云，把他们托向了空中。一阵飘飘然的感觉过后，队员们发现自己被传送到了一座空中花园

“远道而来的客人，我们是守护 Nescafe 之塔的精灵。如果你们想拜访护法和圣主的话，就要由我们引路。因此，你们是不是该给我们一点礼物呢？”

队员们往远处一看，发现花园中有 $n$ 个木箱，$m$ 条柔软的羊毛小路，每条小路的两个端点都是木箱，并且通过它需要 $t_i$ 的时间。队员们需要往每个木箱中放一份礼物，不过由于精灵们不想让花园被过多地踩踏，因此运送礼物的任务最多只能由两位探险队员完成。两位探险队员同时从 $1$ 号木箱出发，可以在任意木箱处结束运送，运送完毕时，每只木箱应该被两位队员中至少一人访问过。运送任务所用的时间是两人中较慢的那个人结束运送任务的时间，求这个时间的最小值

数据范围保证：$n\le 18$

思路分析

定义某个人经过的所有点的集合为 $\mathbf S$，那么我们可以预处理出所有 $f(\mathbf S)$ 表示某个人经过了 $\mathbf S$ 这个点集里的所有点，设全集为 $\mathbf I$，$\overline{\mathbf S}$ 为 $\mathbf S$ 的补集，那么答案为：

$$\text{Answer}=\min_{\mathbf S\in\mathbf I} \left\{\max\left(f(\mathbf S),\min_{\overline{\mathbf S}\subseteq \mathbf T}\left\{f(\mathbf T)\right\}\right)\right\}$$

注意到我们对于每个集合 $\mathbf S$ 都求出 $g(\mathbf S)=\min\limits_{\mathbf S\in\mathbf T}\{f(\mathbf T)\}$，注意到 $g(\mathbf S)$ 可以通过枚举每个 $\mathbf T$ 的时候枚举子集更新做到

最后讲一下如何求出 $f(\mathbf S)$，显然可以考虑 dp，假设 $dp_{\mathbf S,u}$ 表示走完了 $\mathbf S$ 里的所有点，最终停留在 $v$ 的最小代价，那么对于每条边 $(u,v)$ 有转移更新：

$$dp_{\mathbf S\cup \{v\},v}\gets dp_{\mathbf S,u}+w(u,v)$$

注意到可能在 $\mathbf S$ 内部反复转移，因此转移要多做几次

最终 $f(\mathbf S)=\max\limits_{u\in\mathbf S}\{dp_{\mathbf S,u}\}$

最终的时间复杂度 $\Theta(3^n)$

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=18,INF=1e18;
int dp[1<<MAXN][MAXN],f[1<<MAXN],g[1<<MAXN];
inline int bit(int x) { return 1<<x; }
struct node {
	int des,val;
};
vector <node> edge[MAXN];
signed main() {
	int n,m,res=INF;
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;++i) {
		int u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		--u,--v;
		edge[u].push_back((node){v,w});
		edge[v].push_back((node){u,w});
	}
	memset(dp,0x3f,sizeof(dp));
	memset(g,0x3f,sizeof(g));
	dp[1][0]=0;
	for(int S=1;S<bit(n);++S) {
		f[S]=INF;
		for(int turns=1;turns<=n;++turns) {
			for(int u=0;u<n;++u) {
				if(dp[S][u]>=INF) continue;
				f[S]=min(f[S],dp[S][u]);
				for(auto e:edge[u]) {
					int v=e.des;
					dp[S|bit(v)][v]=min(dp[S|bit(v)][v],dp[S][u]+e.val);
				}
			}
		}
	}
	for(int S=1;S<bit(n);++S) {
		for(int T=S;T;T=(T-1)&S) {
			g[T]=min(g[T],f[S]);
		}
	}
	for(int S=1;S<bit(n);++S) res=min(res,max(f[S],g[(bit(n)-1)^S]));
	printf("%lld\n",res);
	return 0;
}