2021 牛客暑期多校训练营 10

AC 代码

A. Browser Games

字典树原题，只不过空间缩写，无法存下 $nm$ 个节点。考虑将无用节点剪去，并将只有一个儿子的节点进行压缩，这样只需要 $n$ 个节点。

F. Train Wreck

每一时刻进行入栈或出栈，对入栈元素进行排序使得没有任意时刻栈内序列相同。首先计算栈内每一层需要入栈的次数，然后按次数从大到小进行排序。然后根据颜色出现次数建立优先队列，每次将剩余数量最多的颜色放入栈中。

H. War of Inazuma (Easy Version)

每一节点会与在二进制下只有一位不同的节点连边。就根据节点二进制下 1 个数的奇偶性进行染色。

总结

开场就想到了 H 的结论，然后花了一些时间模拟 F。只会注意写 A，但由于空间限制的要求，一直想着去优化空间，实际没有成功。也尝试找 D 的规律，最后也未能实现。