禁用STL后如何生存——Amagiii带你水小作业V1

发布于 2020-03-31  1.13k 次阅读


前天深夜,数据结构课程再次留下了小作业。本着在DDL面前愉悦身心的态度,我用两天的时间水完了它们。这里来挂一下十分迷惑的思路和奇奇怪怪的代码。

注意:本篇博文主要面对本班同学,所以我不会在此提供题面、数据范围等信息。如果你没有相关内容说明你不是本篇博客的对象,请自行将鼠标移到页面选单点击图标「x」。

抄代码的就无所谓了,反正我猜我写的像...一样的代码也没有人愿意抄。

3020:

哈夫曼树板题,实现二叉堆即可。

注意每次减少m - 1个元素,所以要补充元素个数到(n - 1) mod (m - 1) = 1,特判m = 2的情况,此时不用补。

代码:

(二叉堆都写炸了,丢~人!)

1358:

类似找点分治中找重心的操作,只不过要你找出所有分割后子块大小小于一半的点。

搜索一遍算出大小,最大的块大小就是max(子树最大大小, n - 该点子树大小)。

代码:

1056:

并查集维护糖与盒子的关系,二叉堆维护盒子中的糖数。(因为p很小,所以可以暴力~)

如果一个堆中一个盒子被取出时发现其所在并查集的根不是自己,则说明它已经被合并掉了,直接丢弃即可。

代码:

4118:

树的不同形态是由c(m, 子树个数)产生的。

前序遍历、后序遍历中,相同字母所控制的一段连续区间一定为同一子树,例如:(a{...},{...}a),所以直接递归即可。

4119:

枚举集合点,树剖lca求距离加和即可。

代码:

4120:

先缩点,考虑所有没有入度的块,它们一定要各问一次,设其数量为x,则答案就是1 - x / n。

注意如果存在一个块,它没有入度,大小为1,且连向的所有块都能被其他块指向,则这个块能用排除法解决。

实际上我不缩点也过了2333

代码:

4180:

有解说明给出的有向边一定构成DAG。拓扑排序,拓扑序小的点指向拓扑序大的点即可。正确性显然。(因为其他边起码不会反着指回来)

4122:

Tire树匹配下单词,然后二分答案,求包含所有可能出现元素的最小区间即可。

滑动窗口,维护计数,基础操作了。

注意n个单词中重复的只算一次。

代码:

(因为没有判0还WA了几发,丢~人!)

4123:

类似「HEOI2016:排序」的线段树解法,枚举答案字符,按照相对大小转为0、1,将区间排序转为区间赋值、区间求和。

代码:

1402:

非旋Treap维护两个标记:赋值、加等差。

注意标记合并顺序为先赋值,后等差。应用赋值时候清除原有一切标记。

代码:

(size * size没转long long挂了一发,丢~人!)

好了,就酱。一堆水题还要发什么题解~还不是要填博客嘛qwq

我也是很难的啦~

对了,zoom课堂用这种头像是不是会被...啊

原图ID:Pixiv 80315592

(什么?没有梯子?这我可不能负责)


Faster than LIGHT