Codeforces Gym

Pro: 8/8/13

Rank: 19/112

签到题

给出一个Treap的创建规则,其权值$y$和键值$x$的关系是$y=\sin x$.求一组数据,把这种方法构造的Treap卡成一条链.

很有意思的数学题.

大致思路是,找到一个初值$k$,要保证$k$这个位置的导数是小于0的.然后找一个稍微比$2\pi$或者其倍数大一点点的数$T$作为周期,然后把$k+xT$作为构造出的序列.这样,每经过一个周期,函数值都会比之前稍微小一点点,就构造出了需要的序列.

然后就是暴力打表找符合要求的数了.下面选的710这个数就非常接近$2\pi$的113倍.

给出一棵树,然后在上面钦定一些点,求能否在树上找到一个点,使得这个点到那些被钦定的点的距离都相等.

结论题.找到距离最远的一对被钦定的点,然后找它们的中点.如果没有中点就不存在,否则答案只可能是这个中点,再BFS一遍检查下是否符合题意就行了.

给出一个长度为$n$的序列$a_{i}$,然后有$q$组询问,每一组询问会给出一个$t$,问能否把原序列分成尽可能小的段数,使得每一小段序列的总和不超过$t$.

对于单个询问,需要贪心算最小的段数.问题是如何求大量的询问.

正解是记忆化+二分答案,通过预处理前缀和,然后每一次通过二分来枚举当前分段的长度,单次询问的复杂度是$\frac{n}{t}\log n$的.因为加了记忆化,所以可以认为$t$是在不断递增的,然后根据调和级数求和就可以知道最后的复杂度是$O(n \log n \log n)$.

我的解法没有用到二分,直接预处理从每个位置开始,向后跳到哪个位置可以使分段的和刚好不超过$2^{i}$.然后对于每个询问,借助这个预处理来进行跳转.中间同样使用了记忆化来处理.时间复杂度理论上是和上面的一样的,实际感觉常数会稍微大一些.

给出空间中的$n$个点,然后要求构造一个尽可能小的四棱锥,使得这个四棱锥可以包住所有的点.要求四棱锥底面的边和坐标轴平行,而且侧面和底面成45度角.

投影到侧面上之后直接处理,然后合并答案.

给出一个拓扑图,保证每条有向边都是从小编号连向大编号.现在这个图的连边情况未知,只知道任意两点间的路径数目对10取模的结果,求原图的连边情况.

先不考虑取模,从小到大枚举$i$,然后从$i-1$到$1$倒序枚举$j$,计算$j$到$i$之前是否有直接连边.通过枚举中间节点$k$,然后检测$j$是否能直接到$k$,如果可以,就把总的方案数减去$k$到$i$的方案数.最后剩下的方案数如果是0说明没有连边,1说明有.

然后把上面的过程放到模10意义下进行.不难发现,最后的结果对10取模一定还是0或1,所以还是可以通过上面的方法直接判断.注意负数对10取模的结果可能还是负数,需要再取一次模转成正的.

给出一个矩形,这个矩形中有一些位置分布着一个大写字母.要求把这个矩形分成若干个小矩形,每个小矩形恰好包含一个大写字母,而且包含A字母的矩形的面积尽可能地大.

先通过悬线法找到包含A的最大矩形,接着对剩下的位置分隔就行了.

签到题

毛子的题目质量还是非常可以的,比如B题出的就很有数学水平.整场的发挥还可以,中期稍有卡顿,但是后期比之前的几次好很多.从罚时上来开还有一些提升空间,比如作为中档题中的签到题的J题应该在更早之前就做出来,K题在给队友用悬线法板子的时候,中间在沟通上出了一些偏差,导致板子使用错误卡了一会.感觉要是可以面对面交流的话应该不会出现这样的情况.

比赛中间的失误还是有的,例如一开始认为J题对10取模后不可做,过了很长时间反应过来才重新提交.H题被经验带歪了,一直认为要通过数据结构维护一些信息来降时间复杂度,这种记忆化询问的方式还是很少见的.