10 2007 档案

• 2007南京赛区总结 by mmd      摘要: 这是我们队的mmd写的总结，发布在珞珈山水bbs上，转载过来。
  
    阅读全文
  posted @ 2007-10-28 23:36 Felicia 阅读(2403) | 评论 (19)  编辑
• The 2007 ACM Asia Programming Contest - Nanjing Final Score Board      摘要: 我们队第6,得到WHU历史上第一枚金牌,这里是Final Score Board
  
    阅读全文
  posted @ 2007-10-28 23:33 Felicia 阅读(906) | 评论 (2)  编辑
• Wish myself      摘要: 临行祝福
  
    阅读全文
  posted @ 2007-10-25 10:03 Felicia 阅读(297) | 评论 (2)  编辑
• [TopCoder]SRM373 Div1      摘要: [TopCoder]SRM373 Div1
  
    阅读全文
  posted @ 2007-10-24 14:02 Felicia 阅读(558) | 评论 (2)  编辑
• [计算几何]pku3293      摘要: 先按规则连。规则是隔一段连一个。比如一条直线上有6个点，就1-2，3-4，5-6，这么连。如果只有奇数个点，就不行。然后再判有没有洞。
  方法是任选一个点，走一圈，看看是否遍历所有的点。
  
    阅读全文
  posted @ 2007-10-22 14:06 Felicia 阅读(591) | 评论 (1)  编辑
• [计算几何]pku3429      摘要: 直接按照题目意思模拟即可。关键是需要实现有理数运算。我的方法是重载运算符。
  
    阅读全文
  posted @ 2007-10-22 13:50 Felicia 阅读(590) | 评论 (3)  编辑
• [计算几何]pku3424      摘要: 先确定窗口左上角可能出现的区域，方法是对每个点确定这样一个区域，然后求交。接下来枚举窗口左上角，计算密码序列，插入一个set中。最后按字典序输出这个set。
  
    阅读全文
  posted @ 2007-10-22 13:48 Felicia 阅读(411) | 评论 (0)  编辑
• [TopCoder]SRM372 Div1      摘要: [TopCoder]SRM372 Div1
  
    阅读全文
  posted @ 2007-10-21 18:34 Felicia 阅读(478) | 评论 (0)  编辑
• ACM/ICPC 2007北京赛区预选赛结果      摘要: ACM/ICPC 2007北京赛区预选赛结果
  
    阅读全文
  posted @ 2007-10-19 20:28 Felicia 阅读(1711) | 评论 (1)  编辑
• [动态规划]O(n^2 / logn)的LCS      摘要: 上次说，LCS有O(n^2 / logn)的解法。这个解法是在字符集不大的情况下，先预处理，再用位运算做状态转移。
  唐文斌曾经翻译过一篇论文，专门讨论这个问题。
  
  下面是练习题（n = 10000 的LCS）
  http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1210
  
  和我的解答
  
    阅读全文
  posted @ 2007-10-19 16:56 Felicia 阅读(1351) | 评论 (5)  编辑
• [动态规划] pku1458 最长公共子序列      摘要: 最长公共子序列……想必很多人都知道吧……
  这里给出一个O(n^2)的算法，人人都会的。
  但是，我想说，我所知道的最好算法，是O(n^2 / logn)的。
  
    阅读全文
  posted @ 2007-10-16 22:46 Felicia 阅读(1403) | 评论 (4)  编辑
• 今天好忙啊      摘要: 忙了一天奖学金的事
  
    阅读全文
  posted @ 2007-10-15 23:46 Felicia 阅读(311) | 评论 (1)  编辑
• [TopCoder]SRM371 Div1      摘要: [TopCoder]SRM371 Div1
  
    阅读全文
  posted @ 2007-10-14 20:41 Felicia 阅读(397) | 评论 (0)  编辑
• 今天很不爽      摘要: 三维凸包郁闷我
  
    阅读全文
  posted @ 2007-10-13 17:44 Felicia 阅读(388) | 评论 (4)  编辑
• [动态规划]pku1080      摘要: 很简单的DP，也是很基础的DP。做法就不说啦：）
  
    阅读全文
  posted @ 2007-10-12 22:25 Felicia 阅读(1098) | 评论 (1)  编辑
• 百度之星2007纪念      摘要: For my A*Star 2007
  
    阅读全文
  posted @ 2007-10-11 19:47 Felicia 阅读(426) | 评论 (4)  编辑
• 第32届ACM-ICPC亚洲区长春赛区预选赛 网络赛选拔结果      摘要: 第32届ACM-ICPC亚洲区长春赛区预选赛 网络赛选拔结果
  
    阅读全文
  posted @ 2007-10-10 09:38 Felicia 阅读(1339) | 评论 (1)  编辑
• [计算几何]pku1379      摘要: 平面点的三角剖分应用。对输入点集进行三角剖分，求得对偶图Voronoi图，Voronoi图的结点以及边与矩形的边的交点就是可疑点。枚举可疑点，计算最优值就是答案。
  
    阅读全文
  posted @ 2007-10-10 09:31 Felicia 阅读(1324) | 评论 (4)  编辑
• [TopCoder]SRM370 Div2      摘要: SRM370 Div2
  
    阅读全文
  posted @ 2007-10-10 09:07 Felicia 阅读(528) | 评论 (2)  编辑
• [动态规划]pku1338      摘要: 非常经典的递推计算。基本思想是设3个指针，分别表示3个素数乘到哪了，然后通过比较3个指针位置的递推结果来确定下一个数是什么。
  具体实现见代码。
  
    阅读全文
  posted @ 2007-10-09 21:53 Felicia 阅读(800) | 评论 (1)  编辑
• [动态规划]pku3420      摘要: 经典题型。如果列数较少，就能用我们熟知的状态压缩DP解决。但现在列数有2^31。考虑到相邻两列之间状态转移规则是相同的，我们可以用矩阵表示这种转移规则，而最后的结果就是求这个转移矩阵的n次幂的左上角元素。
  
    阅读全文
  posted @ 2007-10-08 09:19 Felicia 阅读(1094) | 评论 (0)  编辑
• [动态规划]pku1191      摘要: 不错的DP题。状态f[i][x1][y1][x2][y2]表示要把(x1,y1) -- (x2, y2) 分割成i块所得到的最小平方和（平方和指的是每块矩形的和的平方和）。然后根据水平和竖直切割进行状态转移。这样计算出f[n][1][1][8][8]得到整个棋盘分割成n块得到的最小平方和，然后代入均方差公式算得结果。
  
    阅读全文
  posted @ 2007-10-08 09:12 Felicia 阅读(794) | 评论 (1)  编辑
• [计算几何]两个凸多边形的交      摘要: 两个凸多边形的交
  
    阅读全文
  posted @ 2007-10-07 10:27 Felicia 阅读(1713) | 评论 (2)  编辑
• [图论]pku3417      摘要: 我的做法是，对于每条新边，记录树中与之对应的路径。然后对于每条树边，统计被对应的次数。最后记录每个点到树根的路径上，有多少个1（设为q[i]）。对于新边(x,y)，它对答案的贡献就是q[x] + q[y] - 2q[lca(x,y)]。除了这些，答案还应加上树中0边的数量 * m。
  
    阅读全文
  posted @ 2007-10-06 20:53 Felicia 阅读(494) | 评论 (0)  编辑
• [动态规划]pku1179      摘要: 经典的DP，把环断开，f[i][j][0]记录i到j的最小值，f[i][j][1]记录最大值，然后递推计算。记录最小值是因为两个负数乘起来可能得到一个大的正数。
  
    阅读全文
  posted @ 2007-10-05 16:47 Felicia 阅读(604) | 评论 (0)  编辑
• [动态规划]pku1189      摘要: 概率+DP，比较经典的题。按照递推的方式计算概率。
  
    阅读全文
  posted @ 2007-10-04 20:47 Felicia 阅读(787) | 评论 (4)  编辑
• 第32届ACM/ICPC国际大学生程序设计竞赛 亚洲区南京预选赛 选拔结果      摘要: 详情见内
  
    阅读全文
  posted @ 2007-10-03 18:45 Felicia 阅读(471) | 评论 (0)  编辑
• [计算几何]pku3407      摘要: 简单的几何题，先把经纬度换算成球面坐标，再把球面坐标换算成直角坐标，然后求夹角，乘半径得到球面距离
  
    阅读全文
  posted @ 2007-10-02 17:55 Felicia 阅读(614) | 评论 (1)  编辑
• [计算几何]pku3410      摘要: 我的做法是，枚举第一个多边形的第i条边和第二个多边形的第j条边重合，然后从这条重合的边开始，尽可能的向后扩展重合边，然后判断剩下的多边形是否是凸多边形。
  比赛的时候，我在某个地方忘记对多边形点数求模，导致wa了很久，一直到比赛结束后才AC。以此为鉴！
  
    阅读全文
  posted @ 2007-10-02 17:52 Felicia 阅读(610) | 评论 (0)  编辑
• 奇迹 boa      摘要: 听着很有感觉：）于是找了歌词翻译
  
    阅读全文
  posted @ 2007-10-01 12:27 Felicia 阅读(223) | 评论 (0)  编辑