08 2007 档案

• 点名游戏-被小菜点名了      摘要: 感兴趣的进去慢慢看吧。
  
    阅读全文
  posted @ 2007-08-31 20:02 Felicia 阅读(229) | 评论 (2)  编辑
• [动态规划]pku1947      摘要: 推荐此题。基础树型DP。
  f[x][i](1 <= i <= p)表示以x为根的子树，变成剩下i个点的子树，且剩余子树包含根结点，需要去掉的最少边数。
  那么父结点的f值可以由它所有的儿子的f值做背包得到。
  最后的答案是min(min(f[i][p]) + 1 (2 <= i <= n), f[1][p])
  
    阅读全文
  posted @ 2007-08-31 18:27 Felicia 阅读(856) | 评论 (0)  编辑
• [动态规划]pku1848      摘要: 强烈推荐此题。树型DP。
  分析较长且带有图示，请阅读全文。
  
    阅读全文
  posted @ 2007-08-30 21:47 Felicia 阅读(1029) | 评论 (4)  编辑
• 妹妹的鼓励      摘要: 妹妹说，难题得留着哥哥慢慢解，总会AC的。
  听着心里很是受用呢。
  
    阅读全文
  posted @ 2007-08-29 22:27 Felicia 阅读(150) | 评论 (1)  编辑
• [动态规划]pku1112      摘要: 强烈推荐此题。图论和DP结合。
  分析较长，请阅读全文。
  
    阅读全文
  posted @ 2007-08-29 17:15 Felicia 阅读(907) | 评论 (4)  编辑
• [动态规划]pku2411      摘要: 经典的状态压缩DP。f[i][j]表示第i行，方格排布为二进制数j（第k位上为1表示凸出一个格子，为0表示不凸出）的方案数。用DFS进行状态转移。
  如果行数比较多的话，可以用矩阵乘法优化。因为每行的状态转移都是相同的。设烈数为m，行数为n，可以做到O(2^(3m)logn)。
  
    阅读全文
  posted @ 2007-08-28 21:03 Felicia 阅读(1411) | 评论 (12)  编辑
• [动态规划]pku2288      摘要: 经典的TSP问题变种。状态为f[i][j][k]，表示经过二进制数i所指的哈密顿路（第bi位为1表示经过该点，为0表示不经过该点），倒数第二个点为j，最后一个点为k。.value表示最大权值，.num表示能走出最大权值的路径数。若图中k到p有边，f[i][j][k]则转移到f[i'][k][p]。i' == i | (1 << p)。
  
    阅读全文
  posted @ 2007-08-28 20:47 Felicia 阅读(814) | 评论 (2)  编辑
• 归来还是离去？      摘要:
  
    阅读全文
  posted @ 2007-08-27 22:20 Felicia 阅读(115) | 评论 (0)  编辑
• [动态规划]pku1141      摘要: int f[i][j]表示第i个字符到第j个字符需要添加的最少括号数。string ans[i][j] 表示第i个字符到第j个字符按照最优方案添加括号后的串。状态转移：1.f[i][j]由f[i + 1][j - 1]转移来（通过两端添括号() / [] ）。2.f[i][j]由f[i][k] + f[k + 1][j]转移来（通过串合并）。答案是ans[0][len - 1]。
  
    阅读全文
  posted @ 2007-08-27 15:55 Felicia 阅读(1217) | 评论 (3)  编辑
• [动态规划]pku1050      摘要: 枚举矩形的上边和下边，花费O(n^2)，把问题转化成一维的最大M子段和，做一个O(n)的DP。
    阅读全文
  posted @ 2007-08-26 13:51 Felicia 阅读(1002) | 评论 (6)  编辑
• [动态规划]pku 部分动态规划题目列表      摘要: pku 部分动态规划题目列表
  
    阅读全文
  posted @ 2007-08-26 11:52 Felicia 阅读(6567) | 评论 (5)  编辑
• [计算几何]pku1389      摘要: 题目给出 n 个矩形，要求它们的面积并。具体做法是离散化。先把 2n 个 x 坐标排序去重，然后再把所有水平线段（要记录是矩形上边还是下边）按 y 坐标排序。最后对于每一小段区间 (x[i], x[i + 1]) 扫描所有的水平线段，求出这些水平线段在小区间内覆盖的面积。总的时间复杂度是 O(n^2)。利用线段树，可以优化到 O(nlogn)。
  
    阅读全文
  posted @ 2007-08-25 17:53 Felicia 阅读(435) | 评论 (0)  编辑
• [计算几何]pku1279      摘要: 求多边形的核。用半平面交算法。
  
    阅读全文
  posted @ 2007-08-25 15:56 Felicia 阅读(654) | 评论 (4)  编辑
• [计算几何]pku1418      摘要: 强烈推荐此题！
  先考察一下这个问题的性质。
  性质1：任何一个圆都覆盖了一个闭区域。
  性质2：对于任意一个点，覆盖它的最上面的那个圆，一定是可见的。
  性质3：如果一个圆不可见（它被完全覆盖），那么它的边界是被完全覆盖的。
  性质4：n个圆最多有2(n-1)^2个交点，这些交点把n个圆分成最多2(n-1)^2条小圆弧。
  性质5：对于每个小圆弧，要么它全被覆盖，要么它全不被覆盖。
  根据性质1和性质2，问题转化为恰当地找出一些点，对于每个点，把覆盖它的最上面的圆标记为可见。
  根据性质3，这些点一定在所有圆的边界集合内。
  根据性质5，所有小圆弧构成边界集合。每个小圆弧上只要任意取一个点就能代表整个小圆弧（边界）。不妨取中点。
  至此得到算法：取所有小圆弧的中点，对每个点找到覆盖它的最上面的圆。
  根据性质4，最多取2(n-1)^2个点。对每个点找到覆盖它的最上面的圆，需要O(n)次运算。总复杂度是O(n^3)。
  
    阅读全文
  posted @ 2007-08-24 22:43 Felicia 阅读(526) | 评论 (2)  编辑
• 又是一年仲夏·留给即将短暂离开的土地      摘要: Bless GCC!
  
    阅读全文
  posted @ 2007-08-22 12:07 Felicia 阅读(193) | 评论 (3)  编辑
• [计算几何]pku1269      摘要: 很好的基础题，判断直线相交的情况。要注意精度。判断平行和重合时，用整数运算比较精确。剩下的事就是解出交点了。
  
    阅读全文
  posted @ 2007-08-21 22:30 Felicia 阅读(447) | 评论 (0)  编辑
• [计算几何]pku1118      摘要: 朴素做法是 O(n^3) 的，超时。我的做法是枚举每个点，然后求其它点和它连线的斜率，再排序。这样就得到经过该点的直线最多能经过几个点。求个最大值就行了。复杂度是 O(n^2logn) 的。把排序换成 hash，可以优化到 O(n^2)。
  
    阅读全文
  posted @ 2007-08-21 20:37 Felicia 阅读(462) | 评论 (1)  编辑
• [计算几何]pku2284      摘要: 应用平面图的欧拉定理：V + F - E = 2
  两两线段求交，得到交点数 V，然后判断每个交点落在几条边上，如果一个点在一条边上，这条边就分裂成两条边，边数加 1。这样得到边数 E。最后直接用欧拉定理解得 F。
  
    阅读全文
  posted @ 2007-08-21 17:26 Felicia 阅读(345) | 评论 (0)  编辑
• [计算几何]pku1151      摘要: 题目给出 n 个矩形，要求它们的面积并。具体做法是离散化。先把 2n 个 x 坐标排序去重，然后再把所有水平线段（要记录是矩形上边还是下边）按 y 坐标排序。最后对于每一小段区间 (x[i], x[i + 1]) 扫描所有的水平线段，求出这些水平线段在小区间内覆盖的面积。总的时间复杂度是 O(n^2)。利用线段树，可以优化到 O(nlogn)。
  
    阅读全文
  posted @ 2007-08-21 16:39 Felicia 阅读(544) | 评论 (1)  编辑
• [计算几何]pku1113      摘要: 先求凸包，答案是凸包周长 + 2πl。因为简单多边形的转角是360度，所以加上一个圆的周长。
  
    阅读全文
  posted @ 2007-08-21 15:43 Felicia 阅读(484) | 评论 (0)  编辑
• [计算几何]pku1106      摘要: 简单题，直接模拟即可
  
    阅读全文
  posted @ 2007-08-21 14:35 Felicia 阅读(322) | 评论 (0)  编辑
• [计算几何] pku1265      摘要: 公式很容易猜出，见代码
  
    阅读全文
  posted @ 2007-08-19 16:24 Felicia 阅读(326) | 评论 (0)  编辑
• [计算几何]pku 部分计算几何题目列表      摘要: pku 部分计算几何题目列表
  
    阅读全文
  posted @ 2007-08-19 16:14 Felicia 阅读(3183) | 评论 (12)  编辑
• [计算几何]pku3347      摘要: 先把矩形扩大 sqrt(2) 倍，转化为整点问题。然后逐个求出每个矩形的坐标。
  对于每个矩形分别求出在它之上的矩形覆盖的区间大小 t1，和包括它本身以及在它之上的矩形覆盖的区间大小 t2
  若 t1 == t2，则该矩形被遮盖。
  
    阅读全文
  posted @ 2007-08-15 21:37 Felicia 阅读(391) | 评论 (0)  编辑
• [动态规划]pku3345      摘要: 建立一个虚点（权为无穷大），从它到每个入度为 0 的点都连一条边，然后做树型DP。
  先递归算出子结点的 f 值，然后用背包的方法计算父结点的 f 值。
  
    阅读全文
  posted @ 2007-08-15 18:42 Felicia 阅读(618) | 评论 (0)  编辑
• [计算几何]pku3334      摘要: 二分水面高度，然后求总水量（就是求多边形面积）
  
    阅读全文
  posted @ 2007-08-15 08:59 Felicia 阅读(451) | 评论 (1)  编辑
• [计算几何]pku3335      摘要: 求多边形的核
  
    阅读全文
  posted @ 2007-08-14 19:29 Felicia 阅读(493) | 评论 (0)  编辑
• 2007 校赛总结 by Felicia [2007.4.23]      摘要: 2007 校赛总结 by Felicia
  
    阅读全文
  posted @ 2007-08-14 16:17 Felicia 阅读(444) | 评论 (0)  编辑
• [转载]浅谈ACM/ICPC的题目风格和近几年题目的发展      摘要: 浅谈ACM/ICPC的题目风格和近几年题目的发展
  
    阅读全文
  posted @ 2007-08-14 16:13 Felicia 阅读(609) | 评论 (0)  编辑
• [图论]最大流(类实现)      摘要: 复杂度 O(n^2m)。支持一边构建网络，一边求最大流。每次调用 flow()，得到当前新增的流量。
  
    阅读全文
  posted @ 2007-08-13 21:12 Felicia 阅读(1010) | 评论 (1)  编辑
• [计算几何]pku1696      摘要: 先按题意找出最低点作为起始点，计算出起始向量。然后每次选择左转角度最小的点走。一定能走完 n 个点。
  
    阅读全文
  posted @ 2007-08-13 20:46 Felicia 阅读(489) | 评论 (0)  编辑
• [计算几何]pku1687      摘要: 题目要求从几个区域中，求出包含其它区域的那个区域。其实就是求最大区域。
  只要对每个区域依次计算面积即可，然后取最大的那个。
  
    阅读全文
  posted @ 2007-08-13 19:07 Felicia 阅读(414) | 评论 (0)  编辑
• 凸包(类实现)      摘要: 凸包(类实现)
  
    阅读全文
  posted @ 2007-08-13 14:49 Felicia 阅读(833) | 评论 (0)  编辑
• [计算几何]pku1654      摘要: 记录当前点和前一个点的坐标，算叉积，然后加入总面积之中
  注意最后得到的面积有可能是负的，要取绝对值，还有答案有可能超过 int 范围，要用 long long
  
    阅读全文
  posted @ 2007-08-13 13:42 Felicia 阅读(675) | 评论 (0)  编辑
• [计算几何]pku1556      摘要: 如果两点的连线不和墙相交，那么在图中为这两点连一条边，权值为这两点的距离
  然后做 Dijkstra
  
    阅读全文
  posted @ 2007-08-13 10:34 Felicia 阅读(474) | 评论 (0)  编辑
• 西安赛区总结 by Felicia [2006.12.26]      摘要: 西安赛区总结 by Felicia
  
    阅读全文
  posted @ 2007-08-13 10:27 Felicia 阅读(544) | 评论 (2)  编辑
• 2006上海区域赛总结[2006.11.25]      摘要: 2006上海区域赛总结
  
    阅读全文
  posted @ 2007-08-13 10:25 Felicia 阅读(566) | 评论 (0)  编辑
• 我对11月12日 Moonmist & Deathdecay 北京之行的感想[2006.11.14]      摘要: 我对11月12日 Moonmist & Deathdecay 北京之行的感想
  
    阅读全文
  posted @ 2007-08-13 10:19 Felicia 阅读(421) | 评论 (1)  编辑
• Silence总结[2006.10.15]      摘要: Silence 总结
  
    阅读全文
  posted @ 2007-08-13 10:15 Felicia 阅读(426) | 评论 (0)  编辑
• 单源最短路 Dijkstra O(mlogn) (类实现)      摘要: 单源最短路 Dijkstra O(mlogn) (类实现)
  
    阅读全文
  posted @ 2007-08-13 10:01 Felicia 阅读(816) | 评论 (1)  编辑
• [计算几何]pku1375      摘要: 对每个圆作切线，求出投影区间，最后全部求并
  
    阅读全文
  posted @ 2007-08-12 18:35 Felicia 阅读(357) | 评论 (0)  编辑
• [计算几何]pku1031      摘要: 对多边形的每个边计算和原点的夹角范围，求并得到总夹角范围 alpha
  答案就是 min(alpha, 2 * pi) * k * h
  
    阅读全文
  posted @ 2007-08-12 12:06 Felicia 阅读(884) | 评论 (2)  编辑
• [计算几何]pku1873      摘要: 暴力枚举砍掉的树，然后对剩余的树求凸包
  
    阅读全文
  posted @ 2007-08-12 11:52 Felicia 阅读(465) | 评论 (0)  编辑
• 二分图最大匹配(类实现)      摘要: 二分图最大匹配(类实现)
  
    阅读全文
  posted @ 2007-08-11 21:30 Felicia 阅读(1216) | 评论 (0)  编辑