比赛复盘
浏览所有题后发现所有题都是普及难度。
A。数据范围这么小,暴力 DP 就行。不对 \(10^{40}\) 的答案……要高精度!!尝试了 vector 写高精乘发现异常简单。
B。一年前我就能不看题解独立切。很快写完了。我清晰地记着分数加分数时分子分母要开 __int128。
C。又是小 \({\Omega}\)。显然 \(k = 1\) 答案是 \(n\),\(k \ge 3\) 时答案与 \(10^6\) 同阶,直接暴力。当 \(k = 2\) 时仍然暴力做 \(k \ge 3\) 的,然后去一下重就行。很简单的思想,但是写代码时用了较长时间,因为暴力做的时候直接求幂可能会炸 long long/double。想到了 202? CSP-J T1,手写了 pow 函数就过了所有大样例。
D。一年前我就能不看题解独立切。一年后老师还讲过一遍。写完一遍过大样例。
我去才 \(9:07\)???我 1h AK 了???
赶紧对拍。差不多 10 点左右写完了 genA/genC/genD 和 blA/blC/blD,B 题的 gen 需要构造一个很多要求的 DAG 不想会写。对拍,启动!
A 炸了?C 炸了?D 正常。调试,启动!
找到错是 blA 的 dfs check 挂了,blC 犯了那个可能会炸 long long/double 的错误。改。
又过了一会 A 炸了,原因是高精度应该输出 \(0\) 但我输出空。改。
然后就都没错了。
壮观!
此时是 \(10:22\)。等待。
最后 B 挂了。原因是输出答案也应该输出 __int128。
比赛过程中好的做法和不足
-
做的比较好的地方:差点 AK 了。
-
不足:
- B 挂了。
- 比赛还没结束就写总结。
试题分析
- T1:DP,高精度。
- T2:拓扑排序,小模拟。
- T3:数学,时间复杂度分析(?)。
- T4:前缀和,小模拟。
补题情况
A. 乘积最大
我们可以将 k ++
,然后转化成将数字分成 \(k\) 部分。
\(f(i, j)\) 表示将前 \(i\) 位划分成 \(j\) 部分能得到的最大结果。转移显然。
注意需要高精度。
B. 排水系统
显然是一个 DAG。设 \(f(u)\) 表示第 \(u\) 个水管会排出多少污水。转移 \(f(u) \xrightarrow{+\frac{f(d)}{dout(u)}} f(v)\)。其中 \(dout(u)\) 表示 \(u\) 的出度。
注意可以写一个 struct Frac
,然后重载运算符。
C. 幂次
分类讨论:
- \(k = 1\):答案为 \(n\);
- \(k \ge 3\):此时答案与 \(10^6\) 同阶。暴力即可。
- \(k = 2\):\(1 \sim n\) 内的完全平方数显然有 \(\sqrt n\) 个。先做一遍 \(k \ge 3\)。然后做一个简单容斥即可。
D. 种花
典中典。
枚举 \(\texttt C\) 的左下角,\(\texttt F\) 相当于从 \(\texttt C\) 的左下角往下延申。
前缀和优化。维护最多向右/下延申多少,以及向上并右拐能延伸多少。用到了一些基础的加/乘法原理。
标签:10,暴力,高精度,long,ge,答案,8.28,模拟 From: https://www.cnblogs.com/2huk/p/18384186