2014亚洲区鞍山B题研究

题外话

现场赛与平常比赛的不一样的地方就是：看着很多大水题，现场赛上你就是AC不了。

为什么呢？

时间短，来不及理清思路，来不及看清题意。

题目

比如这次鞍山的B题，看着题目。

题目具体看 。

看着一大坨，但是其实就是操作比较多了罢了。

• Add 增加一个窗口
• Close 关闭一个窗口
• Chat 给最上层的窗口聊天
• Rotate 把第几个移到最上层
• Prior 找到属性最大的那个窗口，移到最上层
• Choose 选择某属性的窗口，移到最上层
• Top 把某属性的窗口置顶
• Untop 取消置顶

分析

假设我们使用链表这个数据结构。

add 操作

对于 add 操作，可以O(1)做到。

但是Add 一个窗口时，那个窗口可能存在，所以我们需要用一个数组或map来标记这个窗口是否存在。

Close 操作

这个我们需要知道这个窗口的位置，所以这里我们就使用map吧，记录下指针的位置。

使用map后我们也解决了判断窗口是否存在的问题。

Chat 操作

这个直接操作最上面的窗口或置顶的窗口即可。

Rotate 操作

由于我们是链表，所以从表头顺着找到第n个即可。

Prior 操作

当初我的想法是使用堆优化或者线段树，后来听说怎么写都不会超时，那就暴力点遍历整个链表查找吧。

Choose 操作

由于我们有map,所以直接就找到那个节点了。

Top 操作

对于置顶的用一个变量来标记。

Untop 操作

这个对标记的标量取反即可，当然需要判断是不是已经标记了。

特殊之处

特殊之处就是题目描述的最后一段，大部分人没有过都是这段理解错的原因。

前面说的还好，最后关闭时一个一个的都说再见。

但是最后一句

he will always sat good bye to the current top girl if he has spoken to her before he close it.

大家都理解为当他把置顶的关闭时，他会说再见。

谁知道，这个 top 不是置顶的那个 top , 而是队列的顶部，置顶的永远在队列的顶部。

好吧，应该很多人都是修改代码，猜测题意，尝试提交过得。

怪不得那么多都是错四五回才AC的。

代码

见我的 github