2020-2021:teams:tle233:nwrussia2019
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:tle233:nwrussia2019 [2020/05/31 16:31] marvolo |
2020-2021:teams:tle233:nwrussia2019 [2020/05/31 16:33] (当前版本) marvolo |
||
|---|---|---|---|
| 行 38: | 行 38: | ||
| 结论题.找到距离最远的一对被钦定的点,然后找它们的中点.如果没有中点就不存在,否则答案只可能是这个中点,再BFS一遍检查下是否符合题意就行了. | 结论题.找到距离最远的一对被钦定的点,然后找它们的中点.如果没有中点就不存在,否则答案只可能是这个中点,再BFS一遍检查下是否符合题意就行了. | ||
| + | |||
| + | ===== [H] High Load Database ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给出一个长度为$n$的序列$a_{i}$,然后有$q$组询问,每一组询问会给出一个$t$,问能否把原序列分成尽可能小的段数,使得每一小段序列的总和不超过$t$. | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 对于单个询问,需要贪心算最小的段数.问题是如何求大量的询问. | ||
| + | |||
| + | 正解是记忆化+二分答案,通过预处理前缀和,然后每一次通过二分来枚举当前分段的长度,单次询问的复杂度是$\frac{n}{t}\log n$的.因为加了记忆化,所以可以认为$t$是在不断递增的,然后根据调和级数求和就可以知道最后的复杂度是$O(n \log n \log n)$. | ||
| + | |||
| + | 我的解法没有用到二分,直接预处理从每个位置开始,向后跳到哪个位置可以使分段的和刚好不超过$2^{i}$.然后对于每个询问,借助这个预处理来进行跳转.中间同样使用了记忆化来处理.时间复杂度理论上是和上面的一样的,实际感觉常数会稍微大一些. | ||
| + | |||
| + | ===== [I] Ideal Pyramid ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给出空间中的$n$个点,然后要求构造一个尽可能小的四棱锥,使得这个四棱锥可以包住所有的点.要求四棱锥底面的边和坐标轴平行,而且侧面和底面成45度角. | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 投影到侧面上之后直接处理,然后合并答案. | ||
| + | |||
| + | ===== [J] Just the Last Digit ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给出一个拓扑图,保证每条有向边都是从小编号连向大编号.现在这个图的连边情况未知,只知道任意两点间的路径数目对10取模的结果,求原图的连边情况. | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 先不考虑取模,从小到大枚举$i$,然后从$i-1$到$1$倒序枚举$j$,计算$j$到$i$之前是否有直接连边.通过枚举中间节点$k$,然后检测$j$是否能直接到$k$,如果可以,就把总的方案数减去$k$到$i$的方案数.最后剩下的方案数如果是0说明没有连边,1说明有. | ||
| + | |||
| + | 然后把上面的过程放到模10意义下进行.不难发现,最后的结果对10取模一定还是0或1,所以还是可以通过上面的方法直接判断.注意负数对10取模的结果可能还是负数,需要再取一次模转成正的. | ||
| + | |||
| + | ===== [K] King’s Children ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给出一个矩形,这个矩形中有一些位置分布着一个大写字母.要求把这个矩形分成若干个小矩形,每个小矩形恰好包含一个大写字母,而且包含A字母的矩形的面积尽可能地大. | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 先通过悬线法找到包含A的最大矩形,接着对剩下的位置分隔就行了. | ||
| + | |||
| + | ===== [M] Lengths and Periods ===== | ||
| + | |||
| + | ==== 题意&题解 ==== | ||
| + | |||
| + | 签到题 | ||
| ====== 总结 ====== | ====== 总结 ====== | ||
| + | 毛子的题目质量还是非常可以的,比如B题出的就很有数学水平.整场的发挥还可以,中期稍有卡顿,但是后期比之前的几次好很多.从罚时上来开还有一些提升空间,比如作为中档题中的签到题的J题应该在更早之前就做出来,K题在给队友用悬线法板子的时候,中间在沟通上出了一些偏差,导致板子使用错误卡了一会.感觉要是可以面对面交流的话应该不会出现这样的情况. | ||
| + | 比赛中间的失误还是有的,例如一开始认为J题对10取模后不可做,过了很长时间反应过来才重新提交.H题被经验带歪了,一直认为要通过数据结构维护一些信息来降时间复杂度,这种记忆化询问的方式还是很少见的. | ||
2020-2021/teams/tle233/nwrussia2019.1590913903.txt.gz · 最后更改: 2020/05/31 16:31 由 marvolo
