题解 | 2015 ACM-ICPC World Finals - Marrakech
题解 | 2015 ACM-ICPC World Finals - Marrakech
A
题意
定义 ,其中 是给定的参数。序列 ,求 。
题解
能成为答案 的只有前缀最大值,答案的 则是 和下一个前缀最大值之间的最小值。从前往后扫一遍即可。
B
C
题意
有一家装备出租公司收到了按照时间顺序排列的 个请求。
这家公司有 个搬运工。每个搬运工可以搬着一套装备按时间顺序去满足一些请求。一个搬运工从第 个请求的位置把东西搬到第 个请求的位置需要一些费用。公司的编号是 ,请求的编号是 。所有搬运工必须从公司出发。
求满足所有请求所需的最小搬运费用。
题解
- 连一条流量为 ,费用为 的边
- 拆成两个点 , 和 间连一条流量为 ,费用为 的边
- 连一条流量为 ,费用为 的边
- 连一条流量为 ,费用为 的边
- 连一条流量为 ,费用为 的边
然后使用有源点上下界可行流。
D
题意
一块正方形的奶酪上有 个球形的孔,孔间不重叠。想要在竖直方向上把这块奶酪切成 片重量相等的奶酪,问每片奶酪的厚度是多少。
题解
球的体积公式是 。球缺体积公式是 或 ,其中 是球体半径, 是球缺的高, 是球缺底面的半径。
直接二分当前奶酪的厚度,用上面两个公式算孔的体积即可。
E
题意
给你 个字符集为 的字符串,你需要将其分成 列,使得每列种相邻的字符串前一个是后一个的子序列,且每列的最后一个字符串都是一个给定字符串 的子序列。
题解
如果这 个字符串中有字符串不是 的子序列,显然 impossible
。
否则,先对字符串按照长度排序。维护两列 。现在加入一个字符串 ,分三类讨论。
- 如果既不能加入 也不能加入 ,则
impossible
- 如果既能加入 也能加入 ,对于这种字符串,我们将其放入一个备胎序列 。要求 中的串满足既能接在当前的 后面,也能接在当前的 后面。如果 非空且 不能能接在 后面,就让 和 接在 后面
- 如果只能加入 或 中的一个,就把 接在该串后面, 接在另一串后面
F
题意
给定一个 行 列的虚拟键盘
,通过上 / 下 / 左 / 右 / 选择
共 个控制键,你可以移动屏幕上的光标来打印文本。
一开始,光标在键盘的左上角,每次按方向键,光标总是跳到下一个在该方向上与当前位置不同的字符,若不存在则不移动。每次按选择键,则将光标所在位置的字符打印出来。
现在求打印给定文本(要在结尾打印换行符)的最少按键次数。
题解
这题只要爆搜 + 剪枝就行。
首先预处理从每个位置往上 / 下 / 左 / 右
跳一格会到哪里,然后大力 BFS。剪枝时可以设 表示经过位置 时最多能匹配到文本串上的哪个位置,转移时如果发现匹配到的位置没有增加,就不用转移(正确性显然)。
G
H
题意
坎儿井是一种灌溉系统,由一条地下的水源和若干条竖直的井组成。
本题中,将其抽象为如上模型。
其中 和 这两条井必须挖。还要在中间挖 条竖井。竖井的横坐标可以是 中的任意实数。挖出来的土必须要送到 (地面)上,每个位置的土可以沿水平方向及竖直方向任意运输,代价即为最短距离。要求你合理安排这 条竖井的位置,使得总代价最小。
I
题意
一条河分为东西方向的 条航道(),每条航道宽为 。
有一个点从 间的某个时间从河岸上的某处(后称原点
)出发,以匀速 从南向北横穿这个游泳池。第 条航道()中有 条船,沿东 / 西
以速度 匀速移动,初始时其船首相对于过原点
南北方向的这条直线的距离是 ,船的长度为 。要求点从到达第 条航道到离开为止,不可以有船穿过这条南北方向的分界线。
求最长的可行出发时间区间的长度。
题解
每条船的信息可以转化为一个 这段时间内不能出发
的限制条件。
具体来说,对于第 条航道内长度为 的船,船头到达这条直线的时刻为 ,船尾离开这条直线的时刻为 , 这段时间内点都不能在航道内。考虑两种极限合法情况,即船头到达直线时点正好离开这个区间,船尾离开直线时点正好进入这个区间。所以点不能在 这段时间内出发。
所以直接差分即可。
J
题意
对于一定长度和宽度的长方形方格纸,在四条边上(不包括角落)选四个点按顺序连成平行四边形。 次询问,问面积在 到 之间的平行四边形中,哪种面积平行四边形数量最多。
题解
平行四边形的面积等于外面矩形的面积减去四个小三角形的面积。
设 表示 的因数个数, 表示面积为 的平行四边形的数量。则 。这显然是一个卷积的形式,直接上 FFT
。
K
题意
给一张简单图 ,至少包含一个环。找到所有的整数 ,使得 中的边可以染成 种颜色,并且所有简单环中的 种颜色的边的数量都相同。
题解
结论题。忽略图中的桥边(这些边显然不会对答案造成影响),对于每条剩下的边 ,计算去掉 后新产生的桥边的数量 ,答案为所有 的 。可以参考证明 ᴮᵃᶜᵏᵘᵖ。
L
题意
考虑 种天气晴 / 多云 / 雨 / 雾
,已知每种天气出现的概率分别为 。现在要传输未来 天的天气情况。想要对这 种可能的天气情况进行二进制编码,并且不存在一个天气情况的编码是另一个编码的前缀。问期望编码长度最小是多少。
题解
哈夫曼编码。对出现概率相同的情况压到一起计算。