题目链接 K-th Closest Distance 这是一道简单的主席树题,思维难点在于是否想到二分。 因为是要求区间[L, R]下标对应数列中的|p-ai|第k小值,如果我们设|p-ai|=x,我
阅读更多...
题目链接 Kingdom of Obsession 这一题需要思维抽象能力,如果仅看到问题的表面(数论),则无从下手。 问题的实质是将1, 2, 3, ..., n这n个数(记为y)与s+1, s+2
题目链接 Equation 注意到等式x+y=z中每个字母只能是一位正整数。 本地预处理所有形如x+y=z的所有可能情况,共有36种。 枚举这36种等式出现与否,同时更新答案。 剪枝:若当前枚举到第i
题目链接 Difference 首先根据f函数的性质可知,f(y,K)的值只与y的各个数位上的数字有关,而与y值本身的大小无关。这一性质暗示可能需要枚举y的数位数字。 根据数据范围进行推算,题中涉及的
题目链接 Car 这一题我做了很长时间,考虑了很多情况。思维题的难度应该属于比既定算法和数据结构还要捉摸不定。 我们需要让车子的速度不断递增,又需要总时间最小。 首先,容易想到差分,预处理出每一段的距
题目链接 Bomb 经典的诠释强联通分量例题,形象地表达了强联通分量的性质和应用。 强连通分量:有向图的一个最大子图满足如下性质——任意两个点u、v,至少有一条路径可从u到达v。 思路:将炸弹抽象为点
题目链接 H - Fishing Master 这道题当年打网络赛的时候是想了一个策略的,但是训练时忘了,所以重新从更加数学的角度思考了一下。 思路:我们总共需要n段钓鱼的时间和n段煮鱼的时间,其总和
题目链接 D - path 图论中使用优先队列的有趣题目,求一张图中第k短的路径。 注意区别于“第k短路”,因为“第k短路”问题是两个定点之间的第k短,而本题没有定点。 注意到第k短的路径最多只有k条
题目链接 C - K-th occurrence 很好的后缀数组题,训练时因为还不会后缀数组,故未做,学习后缀数组后独立写出。 首先第一个问题是如何找出给定子串所有出现的位置。显然,l就是给定子串的首
题目链接 B - array 训练时花了很久才想明白如何建模,这是因为对于权值线段树还没有足够的感觉所致。经过寒假在家中的个人训练,已经初步掌握其常见技巧。我们可以明显地看到,操作1的“+1e7”远大
蔡弈文