返回信息流经过一天的冥思苦想，终于有了点思路，在此就算抛砖引玉。
B(贪心) 这个题我把握不大，为什么我想用贪心法呢？我认为应该尽量避免这样的情况：
现在要确定矩阵的最后一行，然而此时某一列的约束还差 k 个 1 才能满足要求， k>1；
但此时每一列最多能添加 1 个。我的贪心策略是：枚举每一行 i，对列约束数组排序，然
后从大到小取 a[i] 个列，设置相应的列为 1，并把相应的列约束数减 1。
C(贪心) 按时间对题目列表排序，设置一个指针 p 指向表头。然后枚举时间 t (from 1 to
max timelimit)，对于 p 所指题目，若该题目的时间小于等于 t，则将此题目加入做题表；
若此题超时，则考虑难度，如果此题的难度大于做题表中题目的难度的最小值，则将此题
加入做题表，将原最小值的题目删除。
D(动态规划) 这个题目是典型的矩阵和 dp, 用 opt[i,j] 表示数组 a 中从 i 到 j 的子表的均
方值最小和。状态方程是
opt[i,j] = min{opt[i,k]+opt[k+1,j],
k >= i+p-1 && k <= j-p}
E(贪心) 如果题目改为 求一棵树上的最短 hamilton 环长度，很容易就能想到 将所有边都
遍历两次就可以的到一个固定值，无所谓最短。由此，我们可以想到，现在题目要求最短
hamilton 路径长度，那么我们只要找到 最短条件下的 起点和终点，然后用总边权的两
倍 减去 两点之间的简单路径长度就可以了。另一个难点是 如何用高效的算法解决问题，
n = 50000, 如果用时间复杂 n^2 的算法，会超时的。这样想，现在我们还没有确定 起
点终点，可以用构造的方法，找到这两个点，用树的收缩的方法。对于书中的每个节点加
一个域，记录收缩到它的叶结点与它的距离的最大值，每次从度为 1 的点队列中拿出一个
向它的父结点收缩，并将它的父结点的度数减 1， 如果父结点变成叶结点，则加入队列，
直到收缩为一个结点。此时的结点的域记录的就是原树中最长的两点间的简单路径长度。
结点间的父子关系用 dfs or bfs 搜一下就可以确定。
B 把握一般
C 把握较大
D 把握极大
E 把握很大
我只简单说了说思路,不知对不对,请大家帮忙看看。
另外 F 题是个几何题，但是题目的约束比较松，没有提及复杂的多边形，所以不敢讲，
怎么解，我想他们的标程和题目也可能不符。
G,H,I 希望做过的同学，交流一下
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #532同步于 2006/4/3
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
[讨论]昨天 Whu 的比赛总结
sunmoonstar
2006/4/3镜像同步0 回复
订阅后，新回复会通过你的通知中心匿名送达。
0 条回复
暂无回复 · 你可以订阅本帖等待新回复。