2019 ICPC EC Final

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}\left(2\lfloor\frac{i}{2}\rfloor\lfloor\frac{j}{2}\rfloor+\lfloor\frac{i}{2}\rfloor+\lfloor\frac{j}{2}\rfloor\right)$

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)$。

题解：可以发现，$f^k(n)=\sum\prod_{i=1}^k f(a_i)\;(\prod_{i=1}^k a_i = n)$，其中 $a_i \neq 1$ 的 $i$ 最多有 $20$ 个。考虑将 $n$ 拆分为 $m$ 个不为 $1$ 的数的有序拆分方式 $n=\prod_{i=1}^m a_i\;(a_i \neq 1)$，那么每个拆分方式对答案的贡献就是 $C_k^m \cdot \prod_{i=1}^m f(a_i)$。

而 $\prod_{i=1}^m f(a_i)$ 是可以 dp 的。令 $dp_{n,m}=\prod_{i=1}^m f(a_i)$，则:

$$ dp_{n,m}=\begin{cases} f(n) & (m=1)\\ \sum_{d|n,d\neq 1,d\neq n}f(d)dp_{d,m-1}&(m>1) \end{cases} $$

转换一下方程：

$$ \begin{aligned} f^k(n)&=\sum_{i=1}^{20} C_k^i dp_{n,i}\\ f^k(n)&=k \cdot f(n)+\sum_{i=2}^{20} C_k^i dp_{n,i}\\ f(n)&=\frac{f^k(n)-\sum_{i=2}^{20} C_k^i dp_{n,i}}{k} \end{aligned} $$

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 。