Monthly Archives: March 2010

N 个小孩围成一圈，他们被顺时针编号为 1 到 N。每个小孩手中有一个卡片，上面有一个非 0 的数字，游戏从第 K 个小孩开始，他告诉其他小孩他卡片上的数字并离开这个圈，他卡片上的数字 A 表明了下一个离开的小孩，如果 A 是大于 0 的，则下个离开的是左手边第 A 个，如果是小于 0 的，则是右手边的第 -A 个小孩。游戏将直到所有小孩都离开，在游戏中，第 p 个离开的小孩将得到 F(p) 个糖果，F(p) 是 p 的约数的个数，问谁将得到最多的糖果。输出最幸运的小孩的名字和他可以得到的糖果。 首先求出 N 以内最大的反素数，它的因子的个数就是可以得到的糖果数，再根据反素数推出离开者的编号。

卖票插队问题，有 N 个插队行为，告知每次要插到第 i 个位置上，问最后它们的顺序是什么。 建立线段树，每个人最终会被分配在一个叶节点上，从最后一个往第一个开始做插入操作，如果位置被占领，则仿照树的遍历将其放置到另外一个空位置。 参考： http://blog.csdn.net/logic_nut/archive/2009/08/30/4498825.aspx

定义集合的几种操作，包括并、交等，问最终剩下的集合。 这个题目算是线段树比较经典的题目，可以加深对线段树的理解。对于每个节点，必须添加额外的字段。这是线段树的关键。 还有人给起名叫区间树： 区间树和线段数有一定程度的相似： 每个节点都表示一个区间。叶节点都表示单位区间。根节点表示整个全集的区间。 非叶节点的区间都平分成左、右两个子节点。 因此，整棵树是平衡二叉树。 但是区间树和线段树也有完全不同的地方： 区间树的节点上存放的变量及其含义与线段树不同。线段数一般是用来求和的，它的每个节点上存放了该区间内全部数组元素的和。而区间树的节点保存的则是布尔数组在该区间上的覆盖情况：全 1、全 0 或者是未知（需要进一步考查子节点）。 对线段树的每次操作都是针对一个叶节点。在一次操作过程中，只需要牵涉到一条从根到叶的路径，因此其时间复杂度为 O(lg N)。 而对于区间树，每次操作针对的是一个区间，可能会牵涉到多个分枝，但是它的时间复杂度也是 O(lg N)。 强烈推荐此题。 http://imlazy.ycool.com/post.1990834.html

有 N 个房间，有订房和退房操作，订房要求的是选择连续的几个房间，每次订房都是从编号最小的开始，问每次订房操作是否都可以满足。 这个也是线段树，但是节点信息需要进一步丰富。每个节点需要保存几点：当前左子节点最大连续空闲房间、右子节点最大空闲房间数，左右连续空闲房间数。

参考：http://blog.csdn.net/logic_nut/archive/2009/08/30/4497181.aspx 市长竞选，每个市长都往墙上贴海报，海报之间彼此可以覆盖，给出粘贴顺序和每个海报的起点和长度，问最后哪些海报是可见的。 这个题目和木棍涂色类似，但不同的是区间范围太大，你是不可能对 0 到 10000000 的区间来建线段树的。其实更值得关注的是每个海报跨度的地点和终点。将每张海报的起点和终点放到一个数组里，排序之后成为一个新数组 N，假设一张海报的起点和终点为 i 和 j，只要更新 i 和 j 在数组 N 之间的元素就和涂色问题一样处理了。。

这个题目和前面的题目几乎一样，唯一不同的就是 32 位整数可能不够用，得用 64 位的。

两种最常见的解法是所谓的线段树和树状数组。 为每个节点增加 2 个字段，一个表示该节点存放的序列的个数，另一个表示该节点存储的有序的序列，这会导致较大的空间需求。 尽管在整个序列看来是寻找第 k 大的元素，但是在树中，随着搜索的逐步下移，最终会归结为某个节点中所存放序列的折半查找。

和前面那个题目类似，也是涂色，这个是一边涂色一边询问，