2019 ICPC EC Final

From EOJ Wiki
Jump to navigation Jump to search

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)

题意:获得金银铜牌、获得一血、获得全场一血、顽强拼搏都能获得相应的 happiness 。

现在已知其他人的过题时间和错误提交次数,又知道做一道题目所需的时间和或产生的错误提交次数,合理安排做题顺序和时间,使得 happiness 最大。

题解:如果已经确定了自己的做题顺序,显然就只剩下两种情况了:

  • 尽可能快的解决所有题目,显然就是上一道题目结束以后,立即做下一道题目;
  • 为了获得顽强拼搏奖,除了最后一道题目意外,所有题目尽可能快的完成,最后一道题目在其他人的最后一套题目完成的同时完成;

只有 $10$ 道题目,所以可以直接 $10!$ 枚举顺序,然后确定当前方案排名的话,可以通过预处理其他人的排名情况,然后在其中二分。

细节比较多,不过不是很难实现。

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 。