P9314 [EGOI 2021] Railway / 瑞士铁路

题目背景

Day 2 Problem B.

题面译自 EGOI2021 railway。

题目描述

有一条连接苏黎世和卢加诺的长度为 $s$ 千米的铁路。铁路穿过了美丽的阿尔卑斯山，造就了旅程中壮观的景色。由于一些山口对铁路来说太高了，在线路上修剪了 $t$ 条隧道。第 $i$ 条隧道在距离苏黎世 $a_i$ 千米处开始，在 $b_i$ 千米处结束。（因此，第 $i$ 条隧道的长度为 $b_i-a_i$。）

你有一份两地之间的列车时刻表。从苏黎世到卢加诺有 $m$ 班列车，第 $j$ 班列车在 $c_j$ 分钟发车；从卢加诺到苏黎世有 $n$ 班列车，第 $k$ 班列车在 $d_k$ 分钟发车。所有运行中的列车，无论其方向和是否在隧道内，速度均恒为 $1$ 千米每分钟。路程中没有车站，列车也不会在信号灯处停车。因此，每班列车恰好花费 $s$ 分钟到达终点站。

与铁路的长度相比，列车的长度可以忽略不计，所以在本题中，请假设每班列车是一个沿铁路移动的点。

通常情况下，铁路有两条轨道：两个方向各有一条。唯一的例外是隧道。每个隧道只有一条轨道，可以从任何方向通行。

无论何时，只要两班反向运行的列车在隧道外相遇时，他们总是可以安全地经过对方。这包括列车正好在隧道的端点处相遇。但另一方面，如果两班反向运行的列车在隧道内严格${}^{†}$相遇，就会发生碰撞。

已知隧道信息和列车时刻表，请判断是否会发生碰撞。

${}^{†}$严格：原文如此（strictly）。

输入格式

第一行四个整数 $s,t,m,n$——铁路长度、隧道个数、从苏黎世和卢加诺发车的列车数量。

第二行 $t$ 个整数 $a_i$——每个隧道的起点。

第三行 $t$ 个整数 $b_i$——每个隧道的终点。

第四行 $m$ 个整数 $c_j$——从苏黎世发车的时间。

第五行 $n$ 个整数 $d_k$——从卢加诺发车的时间。

输出格式

一行，一个为 YES 或 NO 的字符串，代表是否会发生碰撞。

输入输出样例 #1

输入 #1

100 2 1 4
20 50
30 60
120
30 100 200 250

输出 #1

NO

输入输出样例 #2

输入 #2

1000 1 1 1
600
700
100
400

输出 #2

YES

输入输出样例 #3

输入 #3

1000 1 1 1
600
700
100
300

输出 #3

NO

输入输出样例 #4

输入 #4

1000 1 1 1
600
700
100
500

输出 #4

NO

说明/提示

样例 $1$ 解释

在长度为 $100$ 千米的铁路上，有两条隧道：距离苏黎世 $20\sim 30$ 千米处和 $50\sim 60$ 千米处。唯一一班从苏黎世发车的列车避开了所有从卢加诺发车的列车，如下：

• 与第一班车在距离苏黎世 $5$ 千米处相遇。
• 与第二班车在两个隧道间相遇。
• 与第三班车在距离卢加诺 $10$ 千米处相遇。
• 第四班车在该班车到站后很久才发车。

---

样例 $2$ 解释

两班列车在唯一的隧道中间相撞。

---

样例 $3$ 解释

两班列车在隧道靠近苏黎世的一端相遇。

---

样例 $4$ 解释

两班列车在隧道靠近卢加诺的一端相遇。

---

数据范围

对于全部数据，$1\le s\le 10^9$，$0\le t\le 10^5$，$0\le m,n\le 2\times 10^3$，$0\le a_i<s$，$0<b_i\le s$，$a_i<b_i$，$b_i<a_{i+1}$，$0\le c_j,d_k\le 10^9$，$c_j<c_{j+1}$，$d_k<d_{k+1}$。

在前三个子任务中，保证 $s,c_j,d_k$ 均为偶数。

• 子任务一（$14$ 分）：$t,m,n\le 100$，$s\le 5\times 10^3$。
• 子任务二（$16$ 分）：$t\le 5\times 10^3$，$s\le 10^6$。
• 子任务三（$41$ 分）：无特殊限制。
• 子任务四（$29$ 分）：无特殊限制。另外，$s,c_j,d_k$ 不一定是偶数。

C++实现

//the code is from chenjh
#include<cstdio>
#include<algorithm>
#define MAXT 100005
using namespace std;
int s,t,m,n;
int a[MAXT],b[MAXT];
int c[2002],d[2002];
int main(){
	scanf("%d%d%d%d",&s,&t,&m,&n);
	for(int i=1;i<=t;i++) scanf("%d",&a[i]);
	for(int i=1;i<=t;i++) scanf("%d",&b[i]);
	for(int i=1;i<=m;i++) scanf("%d",&c[i]);
	for(int i=1;i<=n;i++) scanf("%d",&d[i]);
	for(int i=1;i<=m;i++)for(int j=1;j<=n;j++){
		int tm=max(c[i],d[j]);
		int rs=s+c[i]-tm+d[j]-tm;
		if(rs<=0) continue;
		int x=tm-c[i]+(rs>>1);
		int y=upper_bound(a+1,a+t+1,x)-a-1; 
		if(rs&1){
			if(a[y]<=x && x<b[y]) return puts("YES"),0;
		}
		else{
			if(a[y]<x && x<b[y]) return puts("YES"),0;
		}
	}
	puts("NO");
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容