Category: 束发戎马

听ghost讲那oi的事情

Written by 韩光 in 束发戎马 on 二 01 二月 2011. Tags: NOIP,

本人,Joshua Ghost,乃一早就退役的信息学竞赛老鸟是也,本来三次考竞赛成绩都不咋地,本来想忘记这段痛苦的回忆的,但是转念一想,又觉得这样做太不低碳了,以往对我的培训都成了沉没成本,自己也什么都没落下,怪可惜的,所以我下定决心要让自己至少要在oi界留下点什么“我来过”的痕迹……当然不是爪印咯……也就是,打算进行一个“听ghost讲那oi的事情”系列活动!鼓掌!(^o^)/~……诶诶诶,别走别走,也就是在这一系列《听 …

Continue reading »


听ghost讲那最短路的事情之dijkstra算法

Written by 韩光 in 束发戎马 on 二 01 二月 2011. Tags: NOIP, 最短路, 算法, Dijkstra,

图论中的最短路算法,应该是每个进入图论的oier的入门课吧,虽然可能讲一节这个多此一举,但(为了凑数)还是说一说吧~

名称

dijkstra算法

属性

单源最短路算法、巨R眼镜(喂喂喂好像稍稍跑偏了啊……)

来历

在很久很久以前,互联网的规模还没发展到惊天地泣鬼神的时候,网络上的路由器依照静态路由表计算从一个节点(或网络)到另一个节点(或网络)的最短传包路径,就是用的dijkstra算法

思想

首先根据图的情况建立邻接矩阵,从出发点到各个节点的路径都有一个权值(没有道路直接相连置为 …

Continue reading »



听ghost讲那字典树(trie)与AC自动机的事情

Written by 韩光 in 束发戎马 on 五 09 十月 2009. Tags: NOIP, 数据结构, 自动机,

吐个槽先:名字好长!为什么那么长!保持用一格式就那么重要吗!

1.字典树:

字典树,顾名思义,就是把一坨单词以某种树型结构储存起来,当你在这棵树中找寻某个单词的时候,就像查字典一样,一个字母一个字母地筛除不需要的序列。

要实现字典树的这个功能,就需要将有相同前缀的单词存在同一条树枝上,这样一来,字典树除根以外的每个节点都是一个字母(根为空节点),分别以它们为结尾,均可以从树的根开始走出一条字符序列。再标记每个可被视为单词的序列的结束节点,一棵香喷喷的字典树就新鲜出炉啦!这种储存减少了冗余数据的存储,节省空间;查找的时候减少了重复子串的查找,降低了时间复杂度 …

Continue reading »


zoj1013

Written by 韩光 in 束发戎马 on 日 06 九月 2009. Tags: NOIP, ZOJ, 翻译,

哈哈,第二道题的翻译……寂寞……新鲜出炉了!

改了一些题目背景,但是要写的东西还是一样的。

很久很久以前,恩洛斯王国住着一位女王,她的名字叫作Sylvanas Windrunner(希尔瓦娜斯.追风者)。有一天,女王得知她的父亲去世的噩耗,万般悲痛之中,她踏上了参加父亲葬礼的航程。以防万一,她征集了一支禁卫舰队来护航。当她到达目的地--艾拉西亚的时候,她发现了联盟的一座防御塔,那座塔已被战火焚毁。希尔瓦娜斯女王从秘密渠道得知:她的父亲是被一位死亡骑士用毒酒害死的,这使得希尔瓦娜斯女王开始了复仇行动 …

Continue reading »


zoj1011

Written by 韩光 in 束发戎马 on 六 05 九月 2009. Tags: NOIP, ZOJ, 翻译,

老师让做zoj1011上的题,苦于那里都是英文题目,有的大牛用在线翻译站点翻译了一下,让我们更深刻地感觉到“翻译即背叛”……尤其是用电脑翻译……………………

为了使背叛的程度尽可能地减小,咱小菜来人工翻译了一遍,应该还是能读通的把,不通顺或者对题意不明的童鞋,可以留言或者与我qq联系。

我翻译的不是试题,是寂寞…………

非判断性树型自动机(NTA)是一种由多个树型结构组成的设备。每种设备在自己的一种特定的规则下运行,依据这种规则设备中的每个树型结构可以产生一系列的信号,这些信号可以组成一个信号系统。在这个系统里面,其中一个信号叫做“开始信号”,还有一些信号叫做“可接受信号”,其他的信号叫做 …

Continue reading »