数据结构 2021 小作业 4 Hint

[Marcythm]

1123

模拟。

1124

见题目页面中 hint。

1125

见题目页面中 hint。

1126

见题目页面中 hint。

1127

tjm 指点迷津：用 hash 判断字符串相等，询问时枚举哪一位改成什么字符，判断新字符串是否存在。

1128

先做字符串匹配，算出最大单词数，然后滑动窗口找最短区间长度。

1129

直接模拟，用一个数据结构（如堆）维护可出列的 pair，每次出列一对后若这一对两侧的人可组成一对则将其加入数据结构中。

1130

集合最大值随集合大小的增长速率是减小的，集合大小为 $3 \times 10^{4}$ 时最大值仅约 $4 \times 10^{6}$。
暴力搜出集合得到第一个答案，然后贪心删位得到第二个答案。

1131

区间 DP。

1132

同上学期第一次小作业 1012。
如果你要问有什么不一样的话，那就是这次题面没用 $\LaTeX$ 写🌚

1133

并查集记录每颗糖所属的集合编号，用平衡树维护集合大小。

tjm 指点迷津：因为 $p \leq 10$，所以用堆维护即可。

[LibroWu]

1127 trie+dfs也可

[Sakits]

那个复杂度好像不太对？每次查询都有可能把整颗trie跑满

[LibroWu]

确实orz