hankcs的文章

2014-05-22阅读(8470)评论(12)

在解AOJ 0531 Paint Color时，学到了一个累积和的妙用——imos法，由于原文是日语，所以特意翻译过来。值得一提的是，作者Kentaro Imajo跟鄙人同龄，却已取得如此多的成就，而鄙人一无所成，实在汗颜。 imos法 i...

2014-05-22阅读(5522)评论(0)

POJ 2549 Sumsets 子集：从S中找出子集{a,b,c,d}使得 a + b + c = d且d最大。 3.2常用技巧精选（一） 折半枚举 睡不着，A一题提提神。子集最多有1000C4*4个，时限只有一秒。折半枚举有些...

2014-05-22阅读(15871)评论(20)

前言 今天连查带抄地用Java实现了N最短路径，马上要用到自己的分词器里了。 N最短路径其实就是K最短路径（KSP）的变种，KSP指的是DAG中单源路径中前K条最短的路径。求解KSP的算法有删除算法、改进的删除算法（MS Algorithm...

2014-05-20阅读(5036)评论(0)

POJ 3977 Subset 子集：从N个数中挑出非空子集使得和的绝对值最小。 3.2常用技巧精选（一） 折半枚举 子集最多有(2^N)235个，根本枚举不过来。所以折半先枚举前半，记录和及个数。在枚举后半时，使用二分法查找与相反数最相近...

2014-05-20阅读(7298)评论(1)

Bigram语言模型中，分析的是连续两个词的组合概率。问题来了，“1人”和“2人”该怎么操作呢？这两个句子会被当成两种组合“1@人”和“2@人”，如果分别统计共现频次，会导致一个严重的问题，那就是对数词限定太死了，只在1人和2人的情况下能够...

2014-05-20阅读(4803)评论(2)

POJ 2674 Linear world 线性世界：一条线上N只蚂蚁，每只蚂蚁速度固定，方向和坐标不同，碰头后掉头，求最后掉下去那只蚂蚁的名字。 3.2常用技巧精选（一） 弹性碰撞 首先想象整个世界只有一只蚂蚁，于是可以计算出爬行时间最长...

2014-05-18阅读(7954)评论(4)

最近捡起8086汇编，用RadASM编译连接构建之后无法运行，提示“不支持的16位应用程序”。这才想起时过境迁，Win64已经废弃了对16位程序的支持，甚至连debug都废除了。作为老牌RadASM用户，我自然不甘心在虚拟机写汇编，于是摸索...

2014-05-18阅读(5363)评论(1)

POJ 1222 Extended Lights Out 灭灯：有6 * 5的灯，一把下去可能关掉或点亮上下左右中5个灯，希望灭掉所有的灯，求灭灯方案。 3.2常用技巧精选（一） 反转 枚举第一行是否需要按开关就行了，第一行固定了的话，第二...

2014-05-17阅读(17796)评论(19)

当分词系统有一份词典的时候，就可以生成词图了。所谓词图，指的是句子中所有词可能构成的图。如果一个词A的下一个词可能是B的话，那么A和B之间具有一条路径E(A,B)。一个词可能有多个后续，同时也可能有多个前驱，它们构成的图我称作词图。 词图的...

2014-05-16阅读(4273)评论(0)

POJ 3185 The Water Bowls 翻盖有奖：将一列碗翻成口朝上，一把下去可能同时反转3个或2个（首尾），求最小翻转次数。 3.2常用技巧精选（一） 反转 似乎穷举也能过，不过太蠢了。反转法只需枚举2次，分别是从第一个开始翻和...