2019 ICPC EC Final

Replay

Xiejiadong:

• 达成了 ICPC 整赛季全 Au 成就。
• 由于某些原因，队伍三个人在三个不同的房间，似乎成了表面队友。
• Kilo 成功 carry 全场，我全场在梦游。
• 热身赛看到 dls ，就大概猜到了出题人。
• 是很不错的一套题目，让我们根本摸不到模板。
• tlgg 99min 一发过了大模拟太劲了。

Kilo_5723:

Weaver_zhu:

Problem A

Solved by Kilo_5723. 00:11 (+)

Problem B

Unsolved.

Problem C

Solved by Kilo_5723. 02:04 (+2)

Problem D

Unsolved.

Problem E

Solved by Kilo_5723. 03:07 (+1)

Problem F

Unsolved.

Problem G

Solved by Xiejiadong. 04:10 (+2)

Problem H

Solved by Kilo_5723. 04:23 (+6)

Problem I

Unsolved. (-1)

Problem J

Unsolved.

Problem K

Unsolved.

Problem L

Unsolved.

Problem M

Solved by Xiejiadong. 00:52 (+1)

题意：求一个 $\{1,2,3,\cdots ,n\}$ 的 subset $A$ 使得价值最大，价值的计算是：

• 如果 $i\in A$ ，价值加上 $a_i$ ;

• 如果 $i,j\in A,i,j\ge 2$ 切存在正整数 $k(k>1)$ 满足 $i^k=j$ ，价值减去 $b_j$ 。

题解：显然不同的幂次是几个没有任何关联的划分。

元素最多的划分是 $2$ 的幂次，因为 $n\le 10^5$ ，所以最多只有 $16$ 个。

针对每一个不相干的划分，单独统计他们能够取得的最大价值即可。计算的方式是直接暴力 dfs 。