题目大意是一个线段分成n段涂色，有m种颜色可用，给出每种颜色的费用，每一段规定了所用的颜色以及涂色长度区间。同种颜色的涂色长度不能相同，求是否能按要求完成涂色以及最少需要花费的费用。
很典型的搜索题，主要用到了2个减枝技巧：
其中第二个预处理通过O(nl^2)的DP完成。
2353428 2010-11-19 02:08:21 Accepted 2633 C++ 1320 212 IwfWcf
题目大意是在一个布满坑的地图上灌水，求最大储水量。
显然边界的坑是无法储水的，因此可以将边界的坑都加入一个保证坑的高度最小的优先队列（用二叉堆实现）。然后每次取出队列顶端的节点进行四个方向的灌水（如果高度比当前水位高度低则可增加储水量），将未曾加入队列的节点加入队列中继续这个过程直到队列为空即可。因为是从边界开始灌水，可以保证结果的正确性，同时显然可以确定每个坑只进出队列一次。故时间复杂度为O(nmlog(nm))。
7891534 IwfWcf 2227 Accepted 1288K 1719MS G++ 1631B 2010-11-18 18:22:05
题目大意：给出一个有N个数字的环状序列，让你求一个长度不超过k的和最大的连续子序列。
环状的处理方法一般都是在序列的后面补多一段序列。用s[i]表示到第i位的序列和，对于终点位置为i的序列而言，其长度不超过k的和最大的连续子序列的起点位置就是满足min{s[j]}(j = i-k+1..i-1)的j。显然很容易构造数据卡朴素O(nk)的算法，求区间[i-k+1,i-1]内最小的s[j]就是RMQ问题，用二叉堆、Sparse Table、线段树之类的算法或数据结构可以做到在O(logk)的时间内完成查询，因此总的时间复杂度可以优化到O(nlogk)，对于这题的数据规模而言时限是可以接受的。
但通过单调队列可以将时间复杂度优化到O(n)。对于终点为i的序列，每次插入队列的是s[i-1]，显然队尾数值大于等于s[i-1]的元素是可以删除的，这样即可保证队列的单调性。而队首的要求则是位置大于等于i-k。这样对于每个终点为i的数列，队首即为最优起点。而每个位置的元素最多只会进出队列一次，因此可以保证时间复杂度是O(n)。
3144367 2010-11-02 00:19:10 Accepted 3415 609MS 1840K 944B C++ IwfWcf
题目大意就是要求 Sigma( i * Ci ) (i = 1 .. n) 的值最小，{ Ci } 是节点费用的一个排列，同时要满足父节点要出现在子节点前面。
考虑某一个可行解，就是{ Ci }的某一个排列。找到其中的最大值，比如为Ck，它有一个父节点比如Cp。显然Cp要出现在Ck之前。更进一步，Cp就应该出现在Ck的前一个位置。只有这样才有可能Sigma的值最小。不然我们可以将Ck位置向前移动，得到一个更小的Sigma值，并且不破坏上面的约束。既然Cp就出现在Ck的前一个位置，那么它们其实就是连在一起的，可以最为一个整体来看。因此可以把Ck和Cp合并为一个节点，这样就缩小为n-1的规模，缩小后的点的Ci值修改为他们的平均数，然后同样处理即可。这里的平均数，是指两个被合并的集合的Ci值之和除以两个集合的大小之和，譬如两个集合A，B，A的Ci和为Ca，大小为Ta，B的Ci和为Cb，大小为Tb，则合并后为(Ca+Cb)/(Ta+Tb)。7795200 IwfWcf 2054 Accepted 752K 282MS G++ 1288B 2010-10-27 11:33:56
题目大意是给出一个字符串，默认每个字符用8位二进制数（ASCII编码）表示，求以前缀不重复编码压缩后表示字符串所需的最少二进制数位数。
题目中介绍的按频率进行前缀不重复编码的压缩思路其实就是哈夫曼编码的思路，因此只需要构建出一颗哈夫曼树，然后计算原字符串节点的WPL（带权路径长度）即可。构建哈夫曼树的算法是：
此外如果需要求具体的字符编码（即哈夫曼编码），则在树中令所有左分支取编码为 0 ，令所有右分支取编码为1。将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列，就得这个叶子结点所代表的字符的二进制编码。
7794475 IwfWcf 1521 Accepted 756K 16MS G++ 1594B 2010-10-26 23:05:44
题目大意是给出m个虫子的交配组合，确定其中是否存在同性交配现象。
并查集的常规应用是判断两个元素是否处于同一个集合，但这题如果按照这种常规思路构建模型显然是行不通的。于是在常规的模型基础上增加一个数组sex[a]表示节点a与其根节点（注意和父节点相区分）的性别情况，true表示相同，false表示不同。
如果输入的a、b为同一集合中的元素，则直接比较其与根节点的性别情况即可判断是否为同性。如果处于不同集合，则合并两个集合后再进行比较。但合并之后要重新确定被合并的集合的原根节点与现根节点的性别情况。假设a的根节点为c，b的根节点为d，将d合并到c中，那么d相对于c的性别情况有以下可能：
即sex[d] = sex[a] ^ sex[b];
对sex的更新可以在求根节点的同时进行，根据与父节点的性别关系进行处理即可，利用递归实现非常便捷。此外在合并完成之后需要对被合并的集合内的节点的性别关系进行更新，之后再进行同性判断。
7781952 IwfWcf 2492 Accepted 404K 860MS G++ 1315B 2010-10-23 23:55:30
题目大意是一个平面图中相邻（即在同一条边上）的两点不能用同一种颜色染色，求为给出的图染色所需的最少颜色。
先介绍一个定理--“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”，这个定理叫四色定理。基于这个定理，本题中所需的颜色数量不会超过4，因此只需用DFS判断能否用m种颜色完成染色，输出成功的m的最小值即可。
7756121 IwfWcf 1129 Accepted 388K 0MS G++ 1076B 2010-10-17 20:57:54
博文
所有评论
