• 欢迎光临~

Ynoi 切(受)题(虐)记录

开发技术 开发技术 2022-12-18 次浏览

防止忘记做法大致按照切题顺序简略写一下思路,同时造福一下社会。(不过我怀疑大概只有我能看懂我自己写的。)缓慢更新。

  1. P4119 [Ynoi2018] 未来日记

    最初分块。

    人生第一道 Ynoi 和大分块(之前只做过小分块)。也是目前最喜欢的题,感觉思路非常优美。

    序列分块套值域分块。统计次数并做前缀和。修改次数时再做一次差分恢复成原次数数组,改完之后再前缀和回去。同时块内重标号,修改时散块暴力重构;对于整块,如果不会发生合并就直接改标号,会合并就直接暴力重构。考虑发生重构的次数只与块内数字种类数有关,而所有块数字种类最多为 (O(n+m)),每次重构复杂度为 (O(sqrt n)),因此总复杂度 (O((n+m)sqrt n))

    感觉这个写法比很多人写的并查集写法要优美很多,而且复杂度少了个 (alpha(n))

    难度梯度:T2。(Ynoi 内部排序。最高 T0,最低 T4 或者 T5。)

  2. P4117 [Ynoi2018] 五彩斑斓的世界

    第二分块。

    分块套并查集。每次操作即为将 ((i,i-x)) 两种数合并。块内重标号。通过打区间加 tag 使得并查集根节点个数只减不增。所以每块只会发生 (O(sqrt n)) 次合并。时间复杂度 (O((n+m) sqrt n))(本题特殊性质使得并查集复杂度 (O(1))。)空间复杂度 (O(n sqrt n)),会爆。考虑离线逐块处理去一个根号。

    难度梯度:T2.5

  3. P5064 [Ynoi2014] 等这场战争结束之后

    建操作树,在操作树上 DFS。用可撤销并查集维护连通性。顺便维护并查集的时候维护一个值域分块。当块长取 (Oleft(sqrt {frac{n}{log n}}right)) 时,时间复杂度 (O(m sqrt {n log n}))。空间复杂度 (O(m sqrt n))。理论不可过,但是可以调块长以及用 short 卡过去。

    存在空间 (O(n)) 的解法(逐块处理,懒得写)。时间 (O(nsqrt n)) 的做法(top cluster)。

    难度梯度:T3。如果本题 lxl 加强数据使得必须用最优理论时空复杂度才能过的话难度梯度 T1。

之后的有缘在写。

程序员灯塔
转载请注明原文链接:Ynoi 切(受)题(虐)记录
喜欢 (0)