ACM-ICPC 2018 Shenyang Online Contest

ECNU Foreigners

本场代码

Problem B

Solved by ultmaster. 02:42 (+)

题意：正常的算术运算，增加一种运算 d，类似于算术幂：a d b 会产生一个 $[a,ab]$ 区间内的数。求最后表达式的最大值和最小值。

题解：会注意到最后表达式最大最小的时候，每个子表达式一定都是取到最大，或最小的。所以在进行表达式解析的时候算出每个子表达式的最大最小值即可方便地转移。搞清楚文法，写一个自顶向下的 parser 应该很容易。

Problem C

Solved by zerol. 00:47 (+1)

题意：求 $\sum_{i=1}^N \sum_{j=1}^i j^2 \mu^2(j)$。

题解：

[math]\displaystyle{ \begin{eqnarray} &&\sum_{i=1}^N \sum_{j=1}^i j^2 \mu^2(j) \\ &=& \sum_{i=1}^N (N-i+1) i^2 \mu^2(i) \\ &=& \sum_{i=1}^N (N-i+1) i^2 \sum_{d^2 | i} \mu(d) \\ &=& \sum_{d=1}^{\lfloor \sqrt N \rfloor} \mu(d) \sum_{k=1}^{\lfloor \frac{N}{d^2} \rfloor} (N-d^2k+1)d^4k^2 \end{eqnarray} }[/math]

Problem D

Solved by ultmaster. 02:32 (+3)

题意：求第 $k$ 短路是否不超过 $T$。

题解：不会做。但是几百个人过了。不得不去抄。拿下来魔改一下。抄是抄对了，然而 Yes 和 No 搞错了（所以出题人搞这么复杂的一个东西干什么？），然后还反复过样例（其实早就应该不过了但根本没留意）。自闭了大半天，最后还让 zerol 写了一个。浪费了大家的时间，すみません。

Problem E

Solved by kblack. 04:42 (+8)

题意：一共 $N$ 个半径相同圆，求最小的圆覆盖至少 $S$ 个圆。

题解：半径相同所以加在外面就好了。二分半径，枚举圆上一个点，转一圈算一下最大点数，这个部分是循环扫描线。

Problem F

Solved by ultmaster. 00:35 (+)

题意：从一个二分图里面选若干条边，使得每个点的度数都在 $[l,r]$ 内。

题解：从题意很容易看出是一个带下界的网络流（可行流）。下界网络流有经典的建图方法（没书又去网上查）：加超级源点 $S'$ 和超级汇点 $T'$，然后对于每条容量限制为 $[l,r]$ 的边 $x \rightarrow y$，连 $S' \rightarrow y$ 容量 $l$，$x \rightarrow T'$ 容量 $l$，$x \rightarrow y$ 容量 $r-l$；$T \rightarrow S$ 的容量为 $\infty$。如果满载则存在可行流。

Problem G

Solved by kblack & zerol. 01:06 (+)

题意：

题解：最后求 $\sum_{i=1}^n [(i,m)=1] \cdot i(i-1) = \sum_{d|m} \mu(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} i(i-1)$

Problem I

Solved by kblack. 02:01 (+)

题意：给一个编码和校验方式，模拟解码过程。

题解：照着模拟就行了。

Problem J

Solved by zerol. 01:36 (+)

题意：两种操作：1. 树上深度为 d 的点权值加 x。2. 求一棵子树的权值和。

题解：求出 dfs 序。对于所有深度，按照点的个数分类：小于根号的在修改时暴力更新答案，询问时区间查询。大于根号的深度维护前缀和以查询区间中深度恰好为该值的点的个数，询问时逐个累加。总复杂度 $q\sqrt{n\log n}$。

Problem K

Solved by kblack. 00:44 (+2)

温暖的签到，因选手智障而变得冰冷。