A: In this problem, the maximum length of the final sequence is 6, and we
can easily find a basic method of depth-first-search to solve this problem 
with a smaller scale. Since the enhancing levels can be divided into 11 
categories: level 0~level 10, the first optimization is to select the best
6 skills in each category. By this optimization, the skill number N could
be reduced to at most 60. The second optimization is also based on the 11
categories of enhancing levels. We can find the rule that the first skill
will always have no extra damage and the enhancing level of the last skill
is useless. If the enhancing level of each skill in the sequence is 
decided, it is easy to use greedy method to choose the best skills 
available of each category to fit into the sequence. Since the last skill 
has some special properties (we can choose it from any kind and greedy 
method is wrong if we do not consider such properties), we can enumerate 
the skill to fit into the last position, and enumerate the enhancing 
level of the whole sequence, and then use greedy method to fill the blank 
position with its best choice to figure out a solution. The best one 
among these solution will be the final answer. 

B: 将这个简单多边形分成N个有向三角形（即面积可能是负数，就像在求简单多边形
的面积中一样），然后分别求每个三角形同圆公共面积。由于圆心在原点，所以可以
用原点作为划分三角形的“轴点”。

C: 搜索，每次尝试把一个三角形贴着当前未被覆盖区域的边界放置。很多剪枝可用，
例如如果当前边界上有一条边比剩余所有三角形中最短的边还短，那么就不需要继续
搜索

D: 我们用N = 2, W = {1，2}；M = 3, Q = (2, 4, 3) 来说明算法
首先建立3棵几乎相同状态树：
        0                    0                     0
       / \                  / \                   / \
      1  (2)               1   2                 1   2
     /   / \              /   / \               /   / \
   (1)  1   2            1   1  (2)            1  (1)  2
   /   /                /   /                 /   /  
  1   1                1  (1)               (1)  1    
 /                    /                     / 
1                   (1)                    1
区别在于每棵树都有一些节点被标记，表示这个节点对应的砝码堆的总重与Ri相同，
对于每个被标记的节点，向下一棵树的对应节点连一条权为0的边，于是M棵树连成
一个图
从第一棵树的0节点到最后一棵树的被标记节点的最短路长度即为所求
考虑到直接搜整个图（M棵树）所需要的队列可能存不下，所以可以一棵一棵树依次
进行搜索
P.S：facer后来说这题可以进一步改编成加砝码和去砝码用的代价不同（例如取决于
砝码重量），模型相同，不过求最短路需要在树中进行DP

E: 每个formula都可以写成一个2-CNF，例如Xa AND Xb = 0 <=> ~Xa ∨ ~Xb，于是
题目可以转化为2-SAT问题

F: 先搜出来长度不超过T的所有可能路线。然后枚举Tom的起点，计算和并且求出最
大值

G: 最小费用最大流。 离散化每个ai,bi，排序后,变为v1,v2,v3...,vg
增加源点S和汇点T， S到v1增加容量为K,费用为0的边
vg到T增加容量为K,费用为0的边， vi到vi+1增加一条容量为K,费用为0的边
对于题目中给定的线段， 增加ai到bi容量为1,费用为-wi的边
负的最小费用最大流求出的最小费用即为所求
P.S： 比赛中的时限比较紧，只有标程的2倍多；比赛之后放宽了

H: 枚举两条平行y轴的直线, 对两条直线中的点用双端队列处理, 找出最小值
时间复杂度 O(N^3)

• 此帖为潜力帖，鉴定完毕。 (0) ACM06Louty 2008-07-28 16:14:12
• G题600个点的费用流才放2S，模板要非常优秀才行阿。比赛的时候没敢弄，还以为有别的算法。 (2718) TheLordOfTheRings 2008-07-28 16:20:00
• G题可以用带权二部图最大匹配做。 (2718) gubuntu 2008-07-28 16:47:26
  • 运筹学里面讲的单纯形法，好像也可以做吧。 (0) Thank_you 2008-07-28 19:00:23
• Re:果然很符合结题报告的一贯风格 除了语言......... (2718) zhongming 2008-07-28 20:27:58