BUPT 网安杯 游记

Day 0

早上迷迷糊糊的醒来,然后收拾东西一出门…

看不见任何东西,起大雾了

然后迟到了五分钟,虽然大家都迟到了

本来以为航班会延误的…然后它平安无事

通过交易和 StudyingFather 大爷坐在一起,因为各种东西心情复杂,进入睡眠状态

下飞机后坐机场大巴……老师成功的把站名读错了

到达后,服务人员告诉我们可以住两天,但是原来一人一间得变成两人一间,这当然是滋瓷的啦

老师通知完注意事项后,我和 StudyingFather 大爷讨论起午饭的问题,最终决定吃点带北京味道的东西,于是吃了饼子卷菜…

北京消费水平好高啊qwq

吃完饭后依旧心情复杂,继续睡觉=_=

继续阅读“BUPT 网安杯 游记”

随笔 && 公告

因为各种各样的原因,服务器被重做

或许有意或许无意,没有备份主题,而所有友情链接都是存于主题之中的

就这样凭空消失了许多友情链接,我凭借这自己几乎无用的记忆,挽救回了一些友接,其他的就随缘吧

主题终究也是丢了,多多少少算是记录了自己了成长历程的一份代码,说可惜也挺可惜的,但是不抛弃过往终究没有未来

既然博客里有回忆OI路程的,这次,也就回忆一下自己在前端方面的脚印吧

本博客于 2017.01 开始在网上有了自己的身影,随着网站稳定性的不断提高,我开始尝试不断去做一些前端的小东西

最开始写的必应壁纸,当时还打扰了一些比较厉害的人,中间还偷过别人的东西,被别人发现,给自己上了版权这一课

后面逐渐又认识了一些比我年龄稍大的人,自己有了一些越发大胆的想法,写出一个WordPress 主题

再那之后,我总喜欢将自己的闲暇时间用于研究别人的代码,那阵时间是我代码风格最多变的时候,当然,程序里也有不少从他人那里「借鉴」过来的东西,在那之后,我去学习了信息学竞赛,在学习信息学竞赛的空闲时间,将主题的初版写了出来

在那之后,一旦有什么新鲜想法就往主题里面加,直到后来自己也不知道里面都有什么东西,终究不再做大改,转头信息学竞赛,在闲暇时间写一点小东西

到了去年,NOIP 前,完全将自己投入了信息学竞赛当中,利用自己曾经努力的结果,主题也成功被打造的非常适合OI

随着自己代码能力的不断增强,使自己开始能够理解在刚搭建博客时,在 WordPress 官网上所看到那句「代码如诗」的含义

但越是理解,越是不想去学习信息学竞赛中的模板

我不喜欢信息学竞赛中的数学题,因为通常这类题目只能用于解决一个问题–题目中所给予的式子,我们只能将其通过一个个定理化简,一个个到最后都给人一股与原题目无关的感觉

我喜欢像写后端,因为他们可以在现实中有对应,每一行代码从未多余,连起来如诗一般美好,你不知道你的代码会遇到什么,但是你知道你的程序在如何解决问题,你会让你的程序尽力面对所有可能

或许我写下这一段话会被许多Oi大佬们喷,什么我不懂得数学之美,万物基于数学,只是我不理解定理的美妙之处什么诸如此类的话语,我也知道,但这只是一个菜鸡的碎碎念而已

Oi 肯定是要学的,我也喜欢各式各样的算法,在经过一句句代码后,图上的风云变化,一句句代码后,变得有理可循的字符,但是我也真的累了,不想再去分析一句句代码背后的运行速度了

既然服务器坏了,一切重头开始,就让我稍微,回到梦最开始的地方,做一小会的梦吧

私たち、 輝きたい! — Woshiluo 的 2018 总结

00 写在开头

私たち、 輝きたい!

我们,想要闪闪发光!

“2018年真的是有趣的一年呢”,Woshiluo 如是说道

说真的,别说在年初,就是在今年9月,我也想不到我现在会这样,作为一名省队选手在努力,在弱省中,书写着属于自己的篇章……

01 风平浪静的年初

一月初的时候逐渐找到了写作业的感觉,再也不用每天晚上写作业写到老晚了

期末成绩出来,英语满分?进步约100名?

寒假欢乐培训,在3&4班听金哥讲bfs,第一次发现常数问题是如此重要

在2班金哥讲了许多种类的DP,当时第一次接触邻接表,头还是晕的

暑假作业成功全部推到最后一天

期初考试,除去语文,我好像可以年级前十?

这一切听起来都是那么的有希望,仿佛只要今后一直努力下去,身上的兵二校服将会再穿五年

02 抛向湖面上的一颗石头

一次OI上课的机会,杨老师[我的Oi教练]表明了她想将我送去126中的思想,这个话题被在兵二的同班同学听到,回去报告给了班主任?

然后从此在我平静如水的生活中抛进了一块石头,至今它所引起的水波,仍未平静

兵二似乎对这个事情的反应有点大……

正当我企图一步步平静下来这些水波时,在五月份时,杨老师却也发出了最后通碟

兵二代表着稳健的前途,126中代表这遥不可及的梦想

那一阵子,我正在补Lovelive,在某一瞬间内,我也想到了自己,如果自己敢像千歌,像穗乃果一样,向着梦想奔跑,是否,也能够书写出属于自己的奇迹,属于自己的希望 ……

03 追寻着遥不可及的梦想

我最终还是选择来到了126中,每天下午过去学一下听起来很厉害的数据结构与神仙算法,实际上大家都没记住几个,但却对算法水平有了一个不易观察却很重要的提升

每天同时进行着文化课和OI的学习肯定是要付出代价的,过度的熬夜终究使自己在之后相当长一阵时间内的思维迟钝和身体不适,本来就处于亚健康的身体终究还是会隔三差五出现问题

但是那阵时间真的是相当欢乐的……

有着各种各样还算可以看清的目标,可以实现(?)的目标

那时我希望自己能够普及一等,明年参加提高,争取省队

04 宛若繁花般灿烂的暑假

暑假初每天在天百待着基本上就是语文数学OI(数学),当时`15owzLy1`大佬给我们讲数学,听说了好多自己根本没听说过的东西

杨老师告诉我7月底有个网安赛,没人去,我要不要过去凑个数,一问,吃住行参赛费用全免?去去去,西安三日游能不去吗

去了一趟西安,莫名奇妙随便写写就三等奖了?然后原来这比赛还是有奖金的?

感觉莫名奇妙减了不少rp,以及获得一个奥妙重重的称号网安选手

八月初杨老师告诉我们可以去常州集训?仔细想了想,去吧,看看内地的选手

后来被证实被虐成傻逼,不过也获得不少奇怪的加成……

不过也有负buff,养成了Oi考试睡觉的奇怪习惯……

值得一起的是我的手机成功在常州用上了内地的主板

05 接近又远离梦想的NOIP

开学以后,每天依然文化课Oi一同训练,然后 ,但是因为NOIP的原因每天培训时间加长了,身体终于还是打出了GG,要么停课要么放弃Oi,仔细想了想,我是因Oi而来,遂停课

Wahacerdalao向杨老师表明了觉得我可以参加提高组的思想,杨老师同意了这个看法

停课开始还好,过了一个月左右吧,成绩开始出现波动,然后开始疯狂爆炸,基本上每次垫底吧

连杨老师都说了,你这次还是参加普及组吧

那时感觉,自己好像选错了路,为什么不好好学文化课啊 ……

Wahacer Dalao告诉我,按照你自己的想法走就对了

仔细想了一想,还是去提高组一下,算是当经验吧,大体也不会太拉平均分

然后事情的结果就非常有意思了,详见[NOIP2018游记]

06 属于自己的未来

私たち、 輝きたい!

我们,想要闪闪发光

NOIP 成绩出来了,全省第四,XJ没有省选,直接A队

后面上了几天的课,又申请了停课,当我再坐到熟悉的电脑面前的时候,回忆起NOIP时,五味杂陈

开始几天将NOIP前埋的坑都填了(比如某个从NOIP前看到NOIP后的小说)

后来继续向前学,依然觉得什么东西不太对经,约是在12月底的时候我发现,我把Oi,学死了

开始好好认真的举一反三,锻炼思维的时候,已经是停课后两周

果然NOIP前的集训还是对我造成一定的负面心里阴影的

07 尾声

依稀记得Wahacer大佬坚持我应该参加提高组
依稀记得兵二同学们一起努力的次次活动
依稀记得常州淳朴的商店阿姨
依稀记得调到通宵图论
依稀记得调到半夜的Web
依稀记得写到深夜的作业
依稀记得看到半夜的动漫

我超额达成了自己的目标,于今年进入省队

我又有了新的目标,我想在接下来的舞台上闪闪放光

只要朝着梦想奔跑,总有一天会实现的吧?

尽自己努力,做自己最好

]]>

NOIP 2018 游记

用这篇文章,记述自己误打误撞到今天的 OI 路程

Day 0

早上一起来说是有兴Dalao随便看了看去调板子了

结果板子也没调出来,看了一天的番,就当是休息了吧….

下午去七十中看机子,感觉城里的空气竟然比郊区要好

七十中的键盘十分好用,以至于我回到机房都用不习惯自己的键盘了

晚上和15owzLy1大佬一起吃饭,回机房的路上说道:

“这场考试,我就写六道暴力”

这句话,或许是我为数不多的正面Flag

Day 1

提高组

T1: 疑似是原题目???看似还想写个暴力,发现写暴力似乎比写我印象中的正解要难写…没法对拍

T2: 上来觉得是数论,直接就开始写暴力了…写暴力的时候顺便优化了几个地方,一算复杂度貌似是正解?然而我对拍没学,于是自创对拍放后台和优化前的程序拍去了

T3: 对于m=1的部分直接树的直径,不过wahacer讲的时候我没听…自己推了一个出来,后来觉得二分和贪心可做,但是最后因为不可证否就觉得有问题就没写(现在想想不可证否不就是对的吗…血亏)

出来遇到15owzLy1大佬,讨论了一下,听他说他 t2 没写出来,但是 t3 拿了好多暴力分,感觉自己暴力还是不行

普及组

T1: 没啥可以说的,和往年一样,稍微注意一下就不会出事的题目

T2: 题面可以说是非常普及组了,说了一堆最后可以一句话题意的那种,然后我精简题意的时候出了点小问题…

T3: 上来觉得这道题是一个泛化背包…推了大半天然而什么都没有推出来,最后发现随便dp就可以的时候已经写不完了…

T4: 开始觉得哈夫曼编码可做…待我把规律找完写的时候发现…内存会爆炸,然后就弃了这道题目

出来和以前兵二的几个同学和别的几个老朋友对了一下题目,感觉不太对经…

Day 2

提高组

T1: 看到题目的时发现是个基环树…说好这个东西不考的呢?树的部分随便写了些,然后基环树部分因为可以觉得每条边走好几次然后调了半天什么都没有出来,”反正都说了只写暴力了,不写了”

T2: 数学题?暴力暴力暴力,搜索好啊

T3: 第一眼过去觉得是没有上司的舞会让后搞一些比较厉害的东西,不过本着写暴力的心态,直接树形dp走人

下午

“估算一下的话 tg大概 100+100+25+60+25+45=355?”

考完试直接去的一中,遇到Wahacer大佬,给他说了一下我的成绩,就开始疯狂说我省队稳了,当时觉得今年题目还行,可能大家都和我差不多之类的

吃了饭回来,15owzLy1回来说他分数350-400疯狂膜拜大佬

大概聊了一下,感觉好多人都能300+

After

一点NOIP后的小记

我不是jiangtao爷爷,所以自然而然的回到了和机房差一座山的126中去,即使想像15owzLy1他们一样每天到机房,感觉还是艰难

Day +8

大概是CCF说的吧,今天早上十点发布成绩

我请假到一中机房里等成绩

原来每天上午吵吵嚷嚷等着评测结果叨叨题目的人全都不见了

也就只能看到jiangtao c0per15owzLy1在非重要课程的时候翘课过来

这么说来,我似乎很难再看见高二的学长们了呢

心里难受

坐在电脑前面刷了一天官网,成绩还是没出来…

Day +9

不可能以同样的理由请两天假,于是我回到班里,忐忑不安的上了半天的课程,一出来就打开手机看到了成绩

100+100+20+68+20+24=332

感觉还行把

Day2 t3 最后五分钟改的INF结果改锅了,原地爆炸

其他的都基本上是预期以内

总结

提高组

主观问题

  • 数学能力依然有所欠缺
  • 不敢将自己的思维往下想,实现出来
  • 时间规划有细节问题

普及组

主观问题

  • 对长题面把握中心能力有所欠缺

客观问题

  • 上午提高下午普及…
  • 提高题目做多了,思考题目方向有问题
  • 键盘backspace有问题(去年是空格键有问题)

终章

借用 BeyondLimits 博客中的一段话

一个个 OIer 的竞赛生涯总是从一场 NOIP 开始,大多也在一场 NOIP 中结束,好似一次次轮回在不断上演。
如果这次 NOIP 是你的起点,那么祝你的 OI 生涯如同夏花般绚烂。
如果这次 NOIP 是你的终点,那么祝你的 OI 回忆宛若繁星般璀璨。

对于我来说,这场 NOIP 宛若我 OI 生涯中的起点,但我的 OI 生涯能否如同夏花般绚烂?

一切,交给时间,也交给自己

尽自己努力,做自己最好

]]>

单模式串匹配算法 — KMP

KMP

看毛片KMP算法

KMP算法作为一个单模式串匹配算法,以$ O(n+m) $ 的时间复杂度俯视众生吊打各路匹配算法

但是其扩展性的艰难和通用性的低下往往很少用于项目中的实现,但对于我们Oier来说速度才最重要的
KMP的代码量并不大,思维难度也并非其他玄学算法那么高,时间也很优秀,是一种值得用于搞事情的算法

算法理念

传统匹配

在普通的查询算法中,我们通常采用一下的方法:

int ans=0;
for(int i=0;i<alen;i++){
    int t=0;
    while(1){
        if(t>=blen) break;
        if(a[i+t]!=b[t]) break;
        t++;
    }
    if(t>blen) ans++;
}
模式串: ab
文本串: fdsfdfdvab

emmmmm $ O(n) $??优秀

模式串: sb
文本串: sssa

$O(nm)$???什么状况?

好吧,我们知道了,这个东西最快$O(n)$,最慢…$O(nm)$

KMP匹配

显然如果我们在上面的第二个例子中
我们如果能知道,我现在失配了,应当直接更改当前s在模式串中的位置就可以高效的完成匹配

为此,我们定义一个next数组,用「自己匹配自己」的思想,快速找到,当我们适配失败的时候,迅速找到这一位可能在模式串中的位置

这样就避免了往回的问题,大大降低了时间复杂度–$O(n+m)$

代码实现

题目链接: [https://www.luogu.org/problemnew/show/P3375]

#include <cstdio>
#include <cstring>
using namespace std;
int kmp[11000000];
char a[1100000],b[1100000];
int main(){
    scanf("%s",a+1);
    scanf("%s",b+1);
    int alen=strlen(a+1);
    int blen=strlen(b+1);
    int k=0;
    for(int i=2;i<=blen;i++){
        while(k>0&&b[i]!=b[k+1]) k=kmp[k];
        if(b[i]==b[k+1]) k++;
        kmp[i]=k;
    }
    k=0;
    for(int i=1;i<=alen;i++){
        while(k>0&&a[i]!=b[k+1]) k=kmp[k];
        if(a[i]==b[k+1]) k++;
        if(k==blen) {printf("%d\n",i-blen+1);k=kmp[k];}
    }
    for(int i=1;i<=blen;i++) printf("%d ",kmp[i]);
}

KMP 求最小循环节

「KMP这个算法,一般很少考板子题,他通常会给你出一些思维型的,比如,next数组的妙用….」

Next数组的思想不单在KMP中很有用,在对付其他字符串处理问题甚至多模式串匹配中,我们仍将见到他的身影

比如求一个串的最小循环节

很显然len-next[len]即为循环节长度

  • 如果$ len \mod len-next_{len} = 0 $ 则表明字符串是完全由循环解循环构成
  • 如果不是说明需要添加,如果设循环节长度为$L$,则添加的字母个数$ L-len%L = L-next[len]%L $

当然不止这些,至于还有什么吗wq你总会遇到的啦

End

最后,祝rp++

]]>

繁忙过后,一切归平 — 2018 暑假总结

0x01 写在前头

这次的暑假,从中国学生的角度来说可能更本就不是放假,下面这张表是关于我整个暑假的大概情况:

  • 7.1-7.14 天百数学&&信竟
  • 7.14-7.19 一中竞赛机房日常培训
  • 7.20-7.22 西安电子科技大,全国中学生网络安全竞赛
  • 7.23-8.6 一中竞赛机房日常培训
  • 8.6-8.22 江苏常州信息学竞赛集训
  • 8.22-9.1 一种竞赛机房日常培训
  • 9.2 报道

哇我这一个暑假都在干些什么

1×01 数学方面

这个暑假,在数学方面有不少的新知识的输入

  • 7.1-7.14 天百数学

这个是被我们信息学竞赛老师拉过去的,他们高一预科….楞是把我拉上了

知识点:

  • 弧度制
  • 函数的周期性,单调性,奇偶性
  • 指数函数&&对数函数
  • 三角函数入门
  • 集合的交并补

显然,这些知识对我目前还没有什么用,但是在计算机方面学到的东西就比较多:

  • 计算几何初步
  • 排列组合/卡特兰数
  • gcd的各种特性
  • 反演入门
  • 博弈论和SG函数
  • 欧拉函数与积性函数
  • 欧拉筛/线性筛
  • 乘法逆元
  • 高斯消元
  • 矩阵乘法/矩阵快速幂

这些东西考的就比较有用了qwq

经常见到

1×02 信息学方面

数据结构:

  • 平衡树入门
  • 树链刨分
  • 可持久化线段树入门
  • 单调队列/栈

图论:

  • 最大/小生成树
  • 2-sat
  • 网络流入门
  • tarjan

暴力搜索:

  • meet in the middle
  • 玄学剪枝(可行化剪枝&&最优化剪枝)
  • 迭代加深

加强了基础:

  • 二分
  • 线段树
  • 排序

1×03 其他方面

1x03x01 在考试/竞赛方面

  1. 睡眠得当,过多过少过度打乱作息都是大忌
  2. 会不会,先写暴力 有一点是一点,不拿百不拿
  3. 相信自己

1x03x02 其他方面

  1. 假期作业要早规划>_<
  2. 有钱人的家庭难以理解
  3. 不能为利是图,你的心思跟你待久了,别人都会明白
  4. 有其父必有其子
  5. 多和基层人打好关系

2×00 写在最后

这个暑假实际上,比上课的时候还要忙许多,不过,俗话说的好:”痛并快乐着。”你做了什么,就会收获什么

尽自己努力,做自己最好

相信这个世界和你自己

]]>

20180813 考试 解题报告&&题解

T1 吃蛋糕

标准解答就是一看就知道的exgcd

然而本蒟蒻没有看出来写了个错误的小学奥数的解法…

T2 01 串

首先如果你思想没有什么问题的化,30% 的分数还是很好拿上的

标准解答字符串hash

先求出Hash,然后STL强行维护匹配一下…

T3 没有上司的舞会

对于另 30%数据,满足每个会员要么没有上司,要么没有下属。

t

这一部分的数据点就非常的显然了…

维护上司数和下属数,输出最大即可

标准解答玄学网络流,我是真的写不来了wq

]]>