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)

题意：给定一个函数图像上的一些点 $(x,y)$，求一个三段阶梯函数 $f(x)$，使得误差值 $max(y-f(x))$ 最小。

题解：二分误差值。

先将点贪心地加入第一段，再贪心加入第二段，再贪心加入第三段。

点不能全加进去判否，第二段的函数值不可能比第三段小判否。

重要坑点：如果存在 $(0,y)$ 的点，根据题目中的定义，误差值一定要大于 $y$。

Problem F

Upsolved by Xiejiadong && Weaver_zhu && Kilo_5723.

看起来像纸老虎的题目

题意：给出一个表达式，求是否合理或错误。错误指丢到c语言程序里编译不出来的，合理指不论运算符优先级，根据括号运算顺序是唯一的表达式。

题解：根据左括号递归，然后假定它括号里只有一个二元运算。场上以为$a+b+c$不好判感觉写崩了，但实际上假定+和b之间有个左括号继续递归就行了。。。

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Solved by Weaver_zhu. 03:29 (+)

题意：每个字符非'R'即'B'。一共给出$m$个推断，每个推断包含三个字符的判断。要求构造一个字符串满足所有推断中满足三个中至少两个是对的。

题解：比较明显的2-SAT，$no[a] \rightarrow b,c$ 对于三个推断就是建边的方法，最后式子画出来就是$ab+ac+bc+abc$。

Problem L

Upsolved by Xiejiadong && Weaver_zhu && Kilo_5723.

题意：$n$天，$m$人。每个人恰好工作$w_i$天，每天恰好有$d_i$人工作。每个人如果工作一定工作连续$w$天，工作完一定休息至少$h$天。构造一个合理方案或者输出不合法

题解：一个加一引发一整场的wa1。。就是扫一遍可以扫一边求出每天要新加多少人，然后贪心让休息过剩余工作天数尽可能多的人上就行了。注意判断最后每个人是否工作满了$w_i$天。