A

设点 $i$ 有 $a_i$ 个糖果。

对于每个起点 $s$ ,只需要能计算出对于每个点 $t$,完成所有任务所需要的最短时间,取 max 即可。

而计算这个时间相当于是先转几圈,然后找一个距离它最近的当做最后一次的任务。

可以加强到 $10^5$,观察一下 $s \to s+1$ 的变化即可。

B

这个程序相当于每次取这个点最前面的保证和是非负的一段区间。

所以想让它掉进坑一定是前面一堆 $0$,然后一个负数 $-y$,然后一个正数 $x$。那么程序会选择 $x$,而正确的答案可以尝试设计为 $n(x-y)$。

所以我们列出限制:$n(x-y)-x = k$,考虑去枚举 $y$,可以得到 $x=\frac{k+ny}{n-1}$,一定能找到一组解。枚举即可。

C

考虑对于一个串,我们如何计算它能表示的字母个数:设 $f_i$ 表示前 $i$ 个的方案,转移就是 $f_i = f_{i-1}+f_{i-2}+f_{i-3}+f_{i-4}$,从 $f_{i-4}$ 转移的时候要判断一下是否是那些不能用的。

这个题目要统计所有本质不同的子串的答案,我们设 $f_{l,r}$ 表示串 $[l,r]$ 的答案,每次增加一个数可以 $O(n)$ 更新所有右端点是这个的串,我们相当于加了若干个后缀,后缀判重即可。手写哈希表就行了。

加强到 $10^5$?

首先优化 dp:观察转移是 $f_{i,r} = f_{i,r-1}+f_{i,r-2}+f_{i,r-3}+af_{i,r-4}$,可以维护最近的四个线段树,打形如让某个变量加上其他三个的标记,维护和即可。注意标记下放的时候要小心,必须先清空所有标记再做修改。

然后优化找本质不同的子串:发现重复的一定是一段区间,我们求出来后缀数组,相当于找 lcp 的最大值,可以直接按照后缀排序维护一个 set 找一下前驱后继即可。

(纯属自己乱说的,没写过)

D

考虑枚举右端点,给每个左端点记录一个权值 $a_i$ 表示这个区间有多少个只出现一次的数。如果处理出来 $pre_i$ 表示上一个出现的位置,相当于支持给某段区间加一减一,询问权值 $\leq k$ 的数字的和。

这种问题考虑分块。(感觉我还是很少往分块上去想,好难啊)

暴力的做法是对块内维护有序 vector 和整体标记,每次块内二分,复杂度 $O(n \sqrt n \log n)$,可能是过不去的。

一个更好的做法是我们对于每个块维护 $g_{i,j}$ 表示第 $i$ 块权值 $=j$ 的和,然后维护一个整体标记,这样整体标记移动的时候就可以快速更新全局答案了。这里要注意一点细节:由于我们清空一个块的时间必须和长度有关,所以我们必须先清空 $g$ 再去做和块有关的操作,再去重建(当然你存下所有有值的位置也不是不可以)

E

神仙构造题。

取 $1$ 为根。首先求出每个点子树的 $sz_i$。询问只需要询问 $1$ 到其他所有点经过了多少次 $i$ 即可。

然后我们把所有点按照 $sz$ 排序,一个点的所有儿子只有可能在右边。

然后我们现在可以通过每次询问 $1$ 到某个点集经过 $x$ 的数量来判断点集内是否有 $x$ 的儿子,每次二分到最前面的儿子删除即可。这样对于每个儿子只会被询问 $d_i\log n$ 次(大概??),反正能过,

极限数据大概 $6000$ 次。

Last modification:September 24th, 2020 at 09:51 pm
如果觉得我的文章对你有用,请随意赞赏