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)

Problem D

Solved by ultmaster. 02:32 (+3)

Problem E

Solved by kblack. 04:42 (+8)

Problem F

Solved by ultmaster. 00:35 (+)

Problem G

Solved by zerol. 01:06 (+)

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)

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