解题思路

单调栈的基础应用。我们以矩形高度为单位建立一个单调不降的栈，每次输入一个新的矩形高度 h 时，如果新的高度比栈顶高度低，则一直 pop，并累计 pop 出的元素的宽度，每次 pop 我们都可以看做得到一个高度为 h，宽度为累计总宽度的一个矩形（可以看做是把这段的所有矩形高度都削减为 h），用它的面积更新答案。pop 结束后将我们最终得到的新矩形入栈即可。

解题思路

题面中提到后面的人可以找前面的是朋友的人夹塞，让朋友帮忙办理业务，朋友的办理时间会累加。这个过程可以看作一个插队的过程，即把自己插到朋友的后面。由于朋友帮自己办业务是紧接着他自己刚办完的业务连续办理的，所以自己插在朋友后面和让朋友累加办理时间是等价的。

因此我们可以使用队列模拟，每次 pop 出队首，表示此人已办理完毕。接下来找一个人放到队列中作为下一个要办理的人。而下一个的人选是有要求的，即优先寻找一个到达时间不晚于自己离开时间的朋友，让他排在自己后面（插队），如果找不到则按原顺序找自己后面的第一个人，让他排在自己后面。这样不断循环并累加等待时间，直到队列为空即可。

解题思路

题意不难，无非就是把身份证号哈希一下就可以计数了。于是我们可以把身份证号字符串的下标为 0, 5, 10, 15 位置上的字符 ASCII 码累加起来取余 10 当做哈希值的第一位，然后 1, 6, 11, 16 下标的累加和取余 10 当做哈希值的第二位，以此类推，就可以得到一个简单的哈希值。至于如何处理冲突，我这里使用了链地址法（基于 vector 实现），代码写起来比较简单。

如果不想自己写哈希的话，也可以用 map。不过本题如果直接用 string 的 map 是会超时的，但是神奇的是如果换用 long long 的 map 就不会超时哦！

解题思路

每个文件内的单词存放到单独的一个 set 中。询问时直接遍历其中一个 set（必须是 size 较小的那个，否则会超时在最后一个测试点），用 count() 查找另一个 set 中存不存在这个单词即可。做法类似 PAT 上另一道题目「集合相似度」（连示例输出都几乎是一样的）。

Also available: UVALive 6957, Kattis hyacinth, UESTC 1119

题意

在一个网络中给出 n 个节点，每个节点最多可以有两种频率，又给出 n-1 条边（题目保证形成树），要求每条边上的两个节点必须至少有一种频率相同，如果一种频率两个相连的节点所使用，那么这种频率就算做已使用的频率。要求使已使用频率的种数尽可能多，输出每个节点的频率。