2019 ICPC EC Final

From EOJ Wiki
Revision as of 07:05, 17 December 2019 by Kilo (talk | contribs) (→‎Problem C)
Jump to navigation Jump to search

Replay

Xiejiadong:

  • 达成了 ICPC 整赛季全 Au 成就。
  • 由于某些原因,队伍三个人在三个不同的房间,似乎成了表面队友。
  • Kilo 成功 carry 全场,我全场在梦游。
  • 热身赛看到 dls ,就大概猜到了出题人。
  • 是很不错的一套题目,让我们根本摸不到模板。
  • tlgg 99min 一发过了大模拟太劲了。
  • 好像大家 G 题的大部分时间都用来调输入部分了。我用 getchar 只读入 `-` 和数字,似乎一遍就过去了。

Kilo_5723:

  • 对自己发挥还算满意,感觉可能还了一点 CCPC-Final 没怎么上机的债。
  • 题目很棒,每一道题做出来之后都感觉很妙(尤其是某数论求和形状的“构造题”)。

Weaver_zhu:

Problem A

Solved by Kilo_5723. 00:11 (+)

题意:求 $(n+1) \times (m+1)$ 的网格里有多少线段的顶点和中点都在网格端点上。

题解:考虑对每个端点枚举中点的位置。$\sum_{i=0}^{n}\sum_{j=0}^{m}\{2\frac{i}{2}\frac{j}{2}+\frac{i}{2}+\frac{j}{2}\}$

Problem B

Unsolved.

Problem C

Solved by Kilo_5723. 02:04 (+2)

题意:令 $f(x)$ 在狄利克雷卷积意义下的 $k$ 次幂是 $f^k(x)$,已知 $f^k(i) \mod p$,求 $f(i) \mod p\;(1 \le i \le n)$。

题解:

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 。