[GDOI2018]为了不能实现的诺言

Day -1

作为东道主的中山一中,我第一次觉得原来东道主学校要做则么多事情啊!就在我愉快的打着代(颓)码(费)时,被教练叫走去当苦力,清理比赛的机房,即使这并不是我们使用的机子,更不是我们训练的机房,但是天命难违,也只要去做。
附上几张搞清洁的图
[GDOI2018]为了不能实现的诺言-1 ......  查看更多

[GDOI2018]为了不能实现的诺言-续

原本这篇东西我想到是以后心态恢复了我才写的,可是这样的话我也没有这个时间去写了,那么就现在写着吧。

GDOI2018已经正式结束了,在闭幕式当天,我听到最多的一个词莫过于“退役”了,退役的话对已每个选手来说都是一个很痛苦的事情,但也是每一位选手不可缺少的东西,室友经历过才会更加珍惜时间,只有经历过才会变得更加努力和无畏。退役,是竞赛的转折点。
但是现在,我终是要初中退役了,不管怎么说吧,很多人安慰过我,这不重要,高中可以接着搞竞赛,但是一日竞赛人终生竞赛人,竞赛这一点是改不了的了,像毒品一样吧,会上瘾。但是我还是想说一下,不要试图去安慰一个即将退役的选手了,这样完全没有用处,只会使他加剧痛苦罢了,退役这种事,即使经历了无数次,还是会依依不舍不肯忘怀的。所以不要试图安慰他们了,因为你们根本不懂得退役的沉重!这是我作为一个退役选手的感受。
真的你们可能根本不懂得退役的沉重!
对已这些事情,我们能做的只有同情。我是一个不怎么有名气的选手,因为文化课的纠缠,导致了很多矛盾,所以竞赛的时间变得很少了,这样我少了很多时间去复习模板,去刷题,这样导致了我没有进Day3,也因此有了十分之恨
虽然这样,的确是我自己能力的问题,这些事情我经历的太多了,这些除了自己默默承受以外,只能然后重整衣装,再候机会了。
至于为什么在Day4颁奖触景生情,因为别人很多时候问过我,你问什么不在文化课上花同样的时间,为什么没有学好文化课。
这是幻想的问题吧。我对信息学充满着幻想,我相信我可以成功,因为我有这个水平,我有这个兴趣,我有这个环境。
但对于文化课,我也对此充满着幻想,但是一次又一次的失败,让我失去了信心,我相信我可以成功,但是事实给我打打击实在是太大了。于是我就开始躲避这一切。
然后就是退役了,至于为什么退役也和这个有关系,我要回去好好补补文化课了,现在还剩下47天就中考了,即使自己心态爆炸也要好好努力是吧,在这剩下的日子里,我想实现的当初的诺言,即使,有的诺言已经不可能实现了,但是总比一场空好吧。
于是,我按着承诺,退役回去学习文化课,去接受这一切,我希望,这次退役以后,未来我可以更加努力,更加珍惜时间吧。 ......  查看更多

[Usaco2011 Jan]道路和航线

[Usaco2011 Jan]道路和航线
这题一眼看过去就是最短路呢,但是呢?好像有负环,啧啧Dij用不了啦!好像点有点多,Floyd用不了啦,就只剩下spfa啦,但是spfa在极限数据下还是会T掉呢?怎么办,这里引入Spfa其中一个优化SLF优化。全称Small Label First 策略
设要加入的节点是y,队首元素为x,若d[y] \lt d[x],则将y插入队首,否则插入队尾。
其实只要一个优化就可以了,但是为了测试多一下,我就再加了一个优化LLL优化,全称Large Label Last 策略
这样的话我们就可以用上双头队列deque了。
其他的就是普通跑一下spfa就好。
只有SLF优化的 ......  查看更多

[AHOI2005]病毒检测

[AHOI2005]病毒检测
这个可以给出O(n^3)复杂度的代码,肯定就是O(n^3)啦,没有质疑的空间了。那么有什么代码开一跑怎么快呢,DP,DFS,贪心。
这里的话我们就用DP解一下这题
F[i][j]代表母串匹配i个,字串匹配到j个时可不可以匹配到。
然后更新一下,注意*要特判一下,因为他可以匹配很多个字符。 ......  查看更多

后缀排序

后缀排序
这题题目已经告诉你要求些什么了,然后该做什么,当然是求后缀啦,求所有后缀的排名,当然后缀数组啊。这题仅供复习后缀数组的。对于后缀数组,就是先排序再处理,然后每次排一个关键字重复处理直到所有关键字被排序到。 ......  查看更多

[Usaco2012 Dec]First!

[Usaco2012 Dec]First!
这题老旧之前做过,但是好像没调出来T了,然后弃了,现在看到有人在做,然后就顺便丢了出来调了一下调过了。憎恨把true写成false的我。
还找来师兄代码改呀改才改对的。
这题其实真的不难,终点在于你怎么去处理他们之间的关系呢,我们可以先用他们建一棵字典树,然后对所有儿子节点进行拓扑排序,如果有入度为零的点就代表有解。 ......  查看更多

KMP模式匹配算法

纯属为了复习KMP,以前论文丢失了,现在参考算进重新撰写。
简单来说我们可以用O(n)的方法找到所有字串匹配原串的位置,就是基础的字符串匹配算法啦,但是如果暴力的话复杂度是O(nm)。KMP可以通过失败指针进行跳转,省去了直接暴力比对的时间。
失败指针是什么呢?就是下一个这种字串出现的位置在哪里,我们就可以在失败的时候跳去下一个可能可以继续匹配的地方继续询问,而不用暴力枚举。
那么我口胡一下KMP的过程
1. 对字串进行一次自己匹配自己的操作求出Fail数组也就是等会例题代码里面的p数组。
2. 用子串求出来的Fail值匹配母串,记录最长匹配值。
3. 在匹配值里面进行查找,如果又等于子串长度的就是有完全匹配。 ......  查看更多

重复的子串

重复的子串
这题还是KMP裸题,但是呢我们要求出是多少次方。
因为数据保证有解,那么len\%(len-p[len])=0代表有最大重复,然后输出len/(len-p[len])就好

子串是否出现

子串是否出现
这种题目就是KMP算法的基础了,纯属考验KMP熟练程度了,没坑。
这样的话我们就匹配一下看看有没有串的长度是等于子串长度,输出一下开始结束位置就好。