2018-2019 ACM-ICPC, Asia Seoul Regional Contest

ECNU F0RE1GNERS

Problem A

Solved by zerol. 02:10 (+)

题意：给定若干和区间，要求选取两个点，使得尽可能多的区间包含这两个点中的一个。

题解：枚举一个点的位置，然后用线段树维护除去和枚举的那个点有交的剩下的区间的最大的重叠点。

Problem B

Upsolved by ultmaster.

题意：模拟。核心问题是：定义一条路的瓶颈是路径上权值最小的一段。求有向图两两点对间最宽敞的瓶颈。

题解：连 Floyd 都不会了。

Problem C

Unsolved.

Problem D

Solved by zerol. 00:11 (+1)

真·签到。+1 是因为交错 python 版本了。

Problem E

Solved by kblack. 03:15 (+3)

题意：求一个简单分段函数的最小误差最大值估计。

题解：二分然后瞎几吧搞搞，特别注意 0 位置。

Problem F

Solved by ultmaster. 01:51 (+3)

题意：表达式解析，要求判出非法、合法。如果合法，建出表达式树，问是否是一棵二叉树。

题解：如题，模拟。脑残少判了一个地方，自闭一小时。

坑点：经枚举题意，一个节点不算二叉树。

Problem G

Upsolved by ultmaster. (-4)

题意：有三个特工等待时间分别是 $a,b,c$，到达时间是在 $0$ 到 $S$ 之间的均匀分布。等到下一个特工到达就溜溜。求他们能进行两次会面的概率。（题目要求排序，不过其实一样）

题解：不妨假设三人到达时间 $x<y<z$（可以看到刚好占了 $\frac{1}{6}$ 的概率。那么核心问题就是，求 $\text{Pr}(x+a<y \text{ and } y+b<z | x<y<z)$, $x,y,z \sim U(0,S)$, $0<a+b,a+c,b+c<S$。反过来求，运用一下容斥，概率就是 $\text{Pr}(x+a>y \text{ and } y<z) + \text{Pr}(y+b>z \text{ and } x<y) - \text{Pr}(x+a>y \text{ and } y+b>z)$。以 $y$ 作为主变元可以写出积分式：$\int_a^{S} \frac{\text{dy } (y-a)(S-y)}{S^3} + \int_0^{S-b} \frac{\text{dy } y(S-y-b)}{S^3} - \int_{a}^{S-b} \frac{\text{dy } (y-a)(S-y-b)}{S^3}$，化简得到 $\frac{1}{6} [(S-a)^3 + (S-b)^3 - (S-a-b)^3]$。

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Unsolved and Executed.

Problem K

Solved by kblack. 01:32 (+)

题意：一个二进制串，一些人各自猜了三个位置，构造让所有人都猜对至少两个位置。

题解：考虑一个人的三个位置中的任意两个，或一定是真，经典 2-SAT。

Problem L

Solved by kblack. 01:04 (+1)

温暖的贪心，自信减少条件，已枪毙。

_

Problem A

Solved by Xiejiadong. 02:49 (+3)

题意：求两条与 $x$ 轴平行的直线，使得两条直线穿过的长方形最多。

题解：考虑枚举一条直线，那么把这条直线穿过的长方形去掉以后，只需要询问哪个坐标长方形最多。

询问哪个坐标长方形最多，用线段树区间维护即可。

对于删除当前枚举到位置的长方形，用扫描线进行删除插入操作维护。

+3 是因为把 x<<1|1 写成了 x<<1+1 。（此处有一个拟声词）

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

Solved by Xiejiadong. 00:16 (+)

温暖的单词变复数签到。

Problem E

Solved by Kilo_5723. 04:33 (+5)

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Solved by Weaver_zhu. 03:29 (+)

Problem L

Unsolved. (-5)