2011年1月11日

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

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

 

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

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

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

这里有个小技巧,就是标记当前状态是否已经在队列中,防止队列中出现重复状态。具体实现可以参考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

posted @ 2011-01-11 16:21 王之昊 阅读(439) | 评论 (0)编辑 收藏


2010年12月27日

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

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

posted @ 2010-12-27 18:27 王之昊 阅读(410) | 评论 (0)编辑 收藏


2010年11月24日

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

posted @ 2010-11-24 13:16 王之昊 阅读(513) | 评论 (2)编辑 收藏


2010年8月20日

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

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

posted @ 2010-08-20 16:25 王之昊 阅读(207) | 评论 (0)编辑 收藏


2010年7月25日

旋转

posted @ 2010-07-25 12:42 王之昊 阅读(198) | 评论 (0)编辑 收藏


2010年7月4日

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

posted @ 2010-07-04 22:33 王之昊 阅读(220) | 评论 (0)编辑 收藏


2010年7月3日


Stars


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

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

       然后在类似的计算出星座在自身中重复出现的次数B,最后答案为S / B
      
在具体实现上有几个问题:

  • 取整函数的写法:
double round(double d)
{
    return floor(d + 0.5);
}

  • 最开始的速度很慢,分析原因有:
  1. 用了vector,导致变慢, vector确实是慢了,改成数组 1000ms-->204ms
  2. 用了map和set导致变慢,将map改成手写的hash,204ms-->110ms
    • 遇到段错误,结果发现是数组越界,数组越界有上越界(比如数组开小了)和下越界(比如下标为负)

    posted @ 2010-07-03 11:00 王之昊 阅读(262) | 评论 (0)编辑 收藏


    2010年7月1日

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

    posted @ 2010-07-01 19:54 王之昊 阅读(549) | 评论 (0)编辑 收藏

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

          首先一个点的情况最小包围球的半径为0,没有什么意义。
          对于求 n 个点的最小包围球,假设这 n 个点分别为 p1,p2, ..,pn。我们可以先求两个点p1,p2的最小包围球,再求三个点p1,p2,p3的最小包围球,总之在求前 k 个点的最小包围球之前,先求前 k-1 个点的最小包围球。这里的点是已经经过随机洗牌的,假设前k个点的最小包围球是Ck
         
          如果pn被 球Cn-1 所包围,那么Cn=Cn-1;否则Cn一定经过pn,这样我们知道Cn经过的一个点,我们再重复上面的方法重新去算一遍Cn,结果要么是直接确定了Cn,要么是增加一个Cn一定经过的点。然而如果知道4个Cn经过的点,那么这个球也就唯一确定了。

    posted @ 2010-07-01 09:56 王之昊 阅读(961) | 评论 (0)编辑 收藏


    2010年6月30日

    http://acm.pku.edu.cn/JudgeOnline/problem?id=2064

    posted @ 2010-06-30 02:12 王之昊 阅读(323) | 评论 (0)编辑 收藏


    仅列出标题  下一页

    posts - 26, comments - 7, trackbacks - 0, articles - 17

    Copyright © 王之昊