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 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} id(id+1)$，枚举 $m$ 中所有 $\mu$ 不为 0 的因子即可，$i(i+1)$ 前缀和可以 $O(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)

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

One,Two,Three,AK

oxx仅贡献若干模板题以及一道签到……

Problem A

Unsolved. 3:35:49(-1)

Problem B

Solved by oxx1108. 4:32:55(+3)

题意：加了个特殊的计算符号，然后解析表达式求最大值和最小值。

题解：网上拖了个模板改了改，把double改成pair。

Problem C

Solved by dreamcloud & oxx1108. 3:35:01(+3)

题意： [math]\displaystyle{ \begin{eqnarray} f(i)=\left\{ \begin{aligned} 0, i=k\times x^2, x\gt1 \\ i^2 ,else \end{aligned} \right. \end{eqnarray} }[/math]

计算$g(n)=\sum_{num=1}^{n}\sum_{i=1}^{n}f(i)$

题解:首先假设对于所有x都满足$f(x)=x^2$，那么

[math]\displaystyle{ \begin{eqnarray} &&h(n) = \sum_{x=1}^{n}\sum_{i=1}^{x}i^2\\ &=&\sum_{x=1}^{n}\frac{x\times(x+1)\times(2x+1) }{6}\\ \end{eqnarray} }[/math]

上面可以轻易计算出来$h(n)$,接下来考虑$i=k\times x^2, x\gt1$,显然$i^2$被多计算了$(n - i + 1)$次。 $\sum_{i,i=k\times x^2, x\gt1}^{n} i^2 * (n-i+1)=\sum_{i,i=k\times x^2, x\gt1}^{n} i^2 \times (n+1) - i^3 $

[math]\displaystyle{ \begin{eqnarray} &&s(n) = \sum_{i,i=k\times x^2, x\gt1}^{n} i^2\\ &=& \sum_{x = 2}^{x^2 \le n}x^4 \times mu(x)\sum_{i = 1}^{\lfloor \frac{n}{x^2}\rfloor}i^2 \end{eqnarray} }[/math]

Problem D

Solved by Xiejiadong. 1:42:47(+4)

题意：求第k短路。

题解：我们学校似乎上来就开始疯狂的wa......(包括我

然后就以为这道题目有什么特别坑的地方...

其实是大部分人完全没有理解过A-star做最短路的原理(包括我

看到添加了双向边，上来就删了反向遍，没注意到反向边不是无向边的意义，而是建了反图在上面跑SPFA

然后就是板子了

Problem E

Solved by oxx1108. 1:04:33(+1)

题意：问覆盖至少k个圆需要半径至少为多少。

题解：二分答案然后就是个原题，挑战3.6章习题第一个。

Problem F

Solved by oxx1108. 2:12:31(+)

题意：给一个二分图，问能否取若干条边使得满足每个点度数都在[L, R]之间。

题解：裸的上下界网络流。

Problem G

Solved by dreamcloud. 1:41:26(+1)

题意：$a[n] = n \times (n-1)$, 求$\sum_{[i,m]=1}a[i]$

题解：利用容斥，$ans = \sum_{d|m}^{n}mu(d)\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor} a[i\times d]$

Problem H

Unsolved.

Problem I

Solved by Xiejiadong. 4:22:43(+1)

题意：温暖的签到题

题解：题目比较长，比较难理解，一直没人读，到快结束才开的题

由于做题的人比较执杖，数组越界了一发

Problem J

Upsolved by dreamcloud

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

题解：求出 dfs 序，对于所有深度，按照点的个数分类。深度为d的个数小于根号时，则在修改时暴力把所有深度为d的节点在其dfs序处都加上x。个数大于根号的话，则直接在深度为d的前缀和上加上x。对于查询操作，首先查询个数小于根号，直接根据dfs序查询一段区间(套个树状数组)，其次，对于个数大于根号的深度，我们已经预处理出来每个结点含有这个深度的节点个数的数目，一个个累和即可。

Problem K

Solved by oxx1108. 0:23:18(+2)

题意：签到

题解：打表