Difference between revisions of "2019 ICPC EC Final"
Line 36: | Line 36: | ||
题意:令 $f(x)$ 在狄利克雷卷积意义下的 $k$ 次幂是 $f^k(x)$,已知 $f^k(i) \mod p$,求 $f(i) \mod p\;(1 \le i \le n)$。 | 题意:令 $f(x)$ 在狄利克雷卷积意义下的 $k$ 次幂是 $f^k(x)$,已知 $f^k(i) \mod p$,求 $f(i) \mod p\;(1 \le i \le n)$。 | ||
− | 题解:可以发现,$f^k(n)=\sum\ | + | 题解:可以发现,$f^k(n)=\sum\prod_{i=1}^k f(a_i)\;(\prod_{i=1}^k a_i = n$。 |
== Problem D == | == Problem D == |
Revision as of 07:14, 17 December 2019
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)$。
题解:可以发现,$f^k(n)=\sum\prod_{i=1}^k f(a_i)\;(\prod_{i=1}^k a_i = 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 。