C++博客-岁月的童话

求两个正规式之间的编辑距离

王之昊 — Tue, 11 Jan 2011 08:21:00 GMT

求两个正规式之间的编辑距离

正规式与编辑距离都是常见知识，如果不熟悉请见原题^[1]

两个字符串之间的编辑距离的经典解法是动态规划。然而正规式可能包含无穷多个字符串。不好将它转化到两字符串的编辑距离上。另外一个问题，首先要有一种能够识别正规式的方法，就像进行表达式计算时，用递归下降方法来识别就很顺手。

一时之间想不起用什么来表示正规式，后来看到解题报告^[2]才有恍然大悟的感觉，用一个NFA^[3]来表示正规式（编译原理课上学过的，还是重点）。这样状态非常的清晰。

首先将正规式转换成NFA的形式，这样两个正规式，就变成了两个NFA。设表示当前匹配到第一个NFA的x状态，第二个NFA的y状态所消耗的当前最少代价。对于当前的状态寻找他所有的后继，如果发现能够更新后继,那么更新它，并且将它入队，用于更新其他的状态。当队列里空了时候，那么就求到了最小编辑距离。

这里有个小技巧，就是标记当前状态是否已经在队列中，防止队列中出现重复状态。具体实现可以参考UESTC_Melody的代码^[4]，写的非常优美。

引用

[1]http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=5109

[2] http://icpc.amrita.ac.in/2010/images/solution_logic.pdf

[3] http://en.wikipedia.org/wiki/Nondeterministic_finite_state_machine

[4] http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=56951

王之昊 2011-01-11 16:21 发表评论

开始阅读 using OpenMP

王之昊 — Mon, 27 Dec 2010 10:27:00 GMT

OpenMP官方推荐的一本教程。
下载地址为http://www.ppurl.com/2008/12/using-openmp-portable-shared-memory-parallel-programming.html

看这本书的目的是想了解如何写一个并行程序。只有300来页，给自己一个星期大概浏览一遍，对于这种语言类的书一个星期就够了。一天50页。

王之昊 2010-12-27 18:27 发表评论

最后的区域赛

王之昊 — Wed, 24 Nov 2010 05:16:00 GMT

摘要: 福州赛区总结阅读全文

王之昊 2010-11-24 13:16 发表评论

精度小技巧

王之昊 — Fri, 20 Aug 2010 08:25:00 GMT

1.在做多边形切割时，常常先加一个框，框不宜加的过大，比如eps=1e-8，那么框最大不要超过1e7，保证他们的精度之和能够保证在15位之内。这样可以防止在运算过程中出现舍入误差。

2 double的范围是 -1.7*10^(-308) ~ 1.7 * 10^308。超过此范围，可以通过储存他们的指数来保证精度。

王之昊 2010-08-20 16:25 发表评论

旋转

王之昊 — Sun, 25 Jul 2010 04:42:00 GMT

旋转

王之昊 2010-07-25 12:42 发表评论

单调性

王之昊 — Sun, 04 Jul 2010 14:33:00 GMT

http://acm.pku.edu.cn/JudgeOnline/problem?id=1259
the picnic

POJ2823

hdu3401

http://202.120.80.191/state.php?problemid=1016
best cow fence

王之昊 2010-07-04 22:33 发表评论

Stars 坐标旋转

王之昊 — Sat, 03 Jul 2010 03:00:00 GMT

Stars

题意：给你一副星座地图，还有若干星座，对于每个星座，寻找他在地图中出现的次数。其中允许旋转和缩放，若某个星座在地图上的两个映射A，B所包含的点集是一样的，则A，B算一次。

      大致思路是取出星座的第一，第二点，然后枚举这两个点在地图中的位置，将其他的点旋转过去检查是否合法。计算出次数S。

       然后在类似的计算出星座在自身中重复出现的次数B，最后答案为S / B

在具体实现上有几个问题：

取整函数的写法：

double round(double d)
{
return floor(d + 0.5);
}

最开始的速度很慢，分析原因有：

用了vector，导致变慢， vector确实是慢了，改成数组 1000ms-->204ms
用了map和set导致变慢，将map改成手写的hash，204ms-->110ms

遇到段错误，结果发现是数组越界，数组越界有上越界（比如数组开小了）和下越界（比如下标为负）

王之昊 2010-07-03 11:00 发表评论

Deformed Wheel 滚石头

王之昊 — Thu, 01 Jul 2010 11:54:00 GMT

Deformed Wheel

题意：给你一个斜面，再给一个凸多边形的石头，让石头从高出放下，沿着斜面滚动，问石头重心最后的位置。因为摩擦力很大，石头不能滑动，只能转动。（还有很多细节，具体见原题）

      首先，这里要确定什么时候石头算稳定了，可以找到石头和斜面相交的两个点，一个是相对石头的最左点A，一个是相对石头的最右点B，这样如果石头要向左转动，必是绕着A转；要向右转动，必是绕着B转。这里有个问题，如果A，B的横坐标相同，那么A取最低的那个，B取最高的那个。

      找到A,B两点之后，如果重心G 有 A.x<=G.x <= B.x 那么他是稳定的，如果G.x < A.x 那么他是向左转，如果G.x > B.x那么他是向右转。

      其次，要知道石头如果开始转动，不论向左向右，转动多少角度会再次碰到斜面。假设转动theta再次碰到斜面。我们要求出这个theta的值。这里可以采用二分theta的方法来解决，对于某个确定的角度theta1，直接模拟转动theta1角度。看是否超出斜面的范围，如果是，说明theta1大了，否则说明theta1小了。

      二分的实现上我觉得还是有很多trick的，比如

在检查的时候，要检查石头上是否存在一点是否在斜面的下侧，这里很容易忽视那个支点，如果把支点也一并去检查，很可能因为精度的关系判他在斜面的下方，结果check函数一直都是不合法。
向左转和向右转的处理上，向左转我采用的是二分［0，PI］转角，向右转我则是二分［-PI， 0］转角，结果写在一起就出问题了，向左转的判定如果在斜面下方，那么是角度大了，向右转的判定如果在斜面下方，实际上是角度小了，尽管绝对值是大了。还有一种写法是枚举［0，PI］，在check函数里再判断是向左转，还是向右转。这样不容易写错。

王之昊 2010-07-01 19:54 发表评论

Warehouse Location 最小包围球

王之昊 — Thu, 01 Jul 2010 01:56:00 GMT

Warehouse Location

      最小包围球，采用随机增量的方法。时间复杂度O(n)。

      首先一个点的情况最小包围球的半径为0，没有什么意义。
      对于求 n 个点的最小包围球，假设这 n 个点分别为 p1,p2, ..,pn。我们可以先求两个点p1,p2的最小包围球，再求三个点p1,p2,p3的最小包围球，总之在求前 k 个点的最小包围球之前，先求前 k-1 个点的最小包围球。这里的点是已经经过随机洗牌的，假设前k个点的最小包围球是C_k

      如果pn被球C_n-1所包围，那么C_n=C_n-1；否则C_n一定经过pn，这样我们知道C_n经过的一个点，我们再重复上面的方法重新去算一遍C_n，结果要么是直接确定了C_n，要么是增加一个C_n一定经过的点。然而如果知道4个C_n经过的点，那么这个球也就唯一确定了。

王之昊 2010-07-01 09:56 发表评论