AVL
这两天写了个自平衡树,使用子树高度作为判定失衡的依据
贴下代码
1 |
|
参考博客: AVL树(二)之 C++的实现
F.R. | Blog
这两天写了个自平衡树,使用子树高度作为判定失衡的依据
贴下代码
1 | #include<bits/stdc++.h> |
参考博客: AVL树(二)之 C++的实现
是什么让我突然想要写下这一篇小博文呢?
刚刚在写着毛概的读书笔记,选的书很好,是习大大的《谈治国理政》,习大大从非常大的视角对中国近代的发展进行了详实的描述,这让我突然感到一种由内至外的佩服,继而产生了一种恐慌,突然发现自己对历史、政治、美术、摄影、运动、潮流这些等等特别多的领域一无所知。
为什么这么说呢,因为我突然发现,自己已经很久没有认认真真的读过一本所谓的‘闲书’了,无论是无聊闲看的网络小说还是努力钻研的专业书籍,都实在算不得是什么能够提升自己精神层次的东西,或许是高中被语文老师熏陶出的思想素养被我自己挥霍殆尽了吧,现在遇上有些以前三两句自己思想闪光就能被说服的朋友,也常常在辩论中落下下风。
由此我也似乎觉得一些‘闲书’确实是有必要了
另一件事是在看一本小说的时候发生的,看网络小说纯粹是我个人的爱好。但是这本小说确实令人惊艳。
作者从摄影、天文写到历史,细数蔡司徕卡索尼各类摄影器材的发展史,讲解了各类镜头的特性特长,披露了各类商业摄影行业的小伎俩,比如在拍摄可乐的的时候使用机油代替可乐以获得更好的色彩效果等,接着转入天文摄影、战地摄影和严肃摄影的领域,种种摄影技巧和冷门知识着实开拓了我的眼界。
这其中我印象很深的一点是,作者在谈及芬兰时像是不经心的提及了冬季战争,而我对此一无所知甚至百度搜索了才知道这是什么。
冬季战争(芬兰语:talvisota,瑞典语:vinterkriget,俄语:Зимняя война)是一场苏联与芬兰于第二次世界大战期间爆发的苏芬战争,自1939年11月30日由苏联向芬兰发动进攻而展开,苏联最终惨胜芬兰,令其割让与租借部分领土
要知道这部小说的作者据我而知只是一位和我同龄甚至比我还要小一些的年轻人,我惊异于他的博智,同时却又意识到了一点:这才是我们同龄人所应该拥有的知识面宽度。历史如明镜,细数历史的发展,给自己带来历史的智慧应当是每个年轻人都要做到的基本素养。
作者宽广的知识面让我自愧不如,而他有机会接触这些摄影领域的顶级镜头却又让我看到了中国当今的阶级分化,是啊有些人就是有能力为了自己的爱好去收藏一套又一套的价值不菲的镜头,而那镜头只要取一个其价值便足够普通人奋斗几十年。我虽然可能无法拥有这样的财富,却也能通过阅读来了解掌握与其相当的知识,这也可算是一大幸事了。
这个话题或许没有之前的两个话题严肃。
说到流行文化,我的第一反应会是什么呢?pop?音乐节?街绘?文身?酒吧?rap?嘻哈?滑板轮滑?bbox?极限运动?畅快的啤酒?赛车文化?
或许我很难给它下一个定义。因为除了这些很明确能和流行文化牵扯起来的东西外,也是存在很多流行的东西的,只是他们无法被直接冠上流行文化的名字。这种事情,一千个人心中有一千个哈姆雷特吧。
姑且限定下范围好了,如果把所有‘我们这一代的人会被吸引去做的’或者‘那些能彰显年轻生命的活力的事情’称作流行文化的话。那其实很多东西比如二次元,又或是小圈子的宅男腐女也是可以被称作流行,他们平时自认为自己是身处一个’圈子’,可须知这样的圈子随处都是,只是不为大众所知而已,这些也可以称作流行。
那我先从传统的流行音乐文化开始吧,或许我接下来说的有不对那请联系我说服我。流行音乐其实是个非常容易过期的东西,像是十年前的lady gaga,便是现在她的许多歌听着也还算是挺不错,可是却少有人去听了,因为流行的特点就是快速的流行和快速的过期。有的流行音乐成为了经典如《海阔天空》,更多的则在时间的冲刷下被快速遗忘。有很多的流行音乐包括一些现在的民谣风,都是那种听一次惊艳,听多了反而会厌烦的歌,因为它们少有能真正抓住人心灵的内涵,而自身的华丽惊艳只是喧闹嘈杂的同义词。所以经常在后来的更多更好听的旋律前败下阵来。
流行街头文化我接触的不多,只是略微知道一些诸如滑板轮滑街绘街舞这类,轮滑是我认真想过去学的,平地花式轮滑确实是一种不危险又很酷的运动,可惜最后没有毅力坚持下去。在我看来,这确实是一个既美丽又完美的生态,玩家通过轮滑文化得到了自己想要的炫酷体验,轮滑赚到了钱又用这钱去反馈生态,以至于生生不息,充满了年轻的朝气。潮流向来是烧钱的,这些年轻人却也付钱付的心甘情愿,那也还好。
嘻哈说唱文化是我的一个朋友带我体验的,在这之前,我对嘻哈的认识停留在b榜上黑人音乐的脏词以至于对嘻哈有种本能的排斥,但是这个朋友带我体验了一些华语嘻哈歌曲后我放下了这些偏见,有些歌曲确实是优秀到听了一遍还想听第二遍,比如陈冠希的《外星伴侣》《战争》等,后来我对黑人嘻哈音乐也有了一些包容之心,因为后来无意间看了Drake的一个MV,他在MV里的这首歌充斥着黑人嘻哈的各种symbol如钱、奢侈品、女人、毒品、跑车等,但MV的内容却是他给黑人贫民送去钱帮助他们的生活,说实话这让我对黑人ganstar有了很大改观。
突然换个方向希望不要介意哈哈。
饭圈文化我接触的不深却有很长时间的了解,说实话在刚刚接触饭圈的时候确实会感觉不可思议,怎么会有人为了明星或者为了一部作品自己不远千里前去‘朝圣’,但是随着我的了解,我发现这些人其实是有某种我没有的东西的,比如她们可能为了自己粉了的一个明星的消息而突然高兴或者突然沮丧,这种在我看来神秘的敏感或许就是她们不同于其他人的地方吧,或许正是这份敏感无处安放所以才会有如此风起云涌动荡的饭圈吧。
(突然思路被打断正好现在也有点太晚了那就这样吧)
这段时间我的主要感受还是…或许我快要找到我自己生活的方向了
嗯差不多就会是这样
F.R.
19年5月5日凌晨
代码存档
1 | #include<bits/stdc++.h> |
注意压缩空间之后完全背包几乎和01背包一模一样,只是j的遍历方向01背包为反向,而完全背包的为正向。
参考博客:
裸题:
代码存档
1 | #include<bits/stdc++.h> |
so,CI能做什么?
有了CI,就无需每次进行hexo d -g,减少了中间的复杂步骤
只需要在写博前git pull到本地,写完后调试没问题就git push上去就行
更多内容可以去travis-CI官网了解https://www.travis-ci.org/
Treap是一种码量极小的平衡二叉树,是一种结合二叉树和二叉堆的数据结构。
Treap通过不断的split和merge来维护平衡二叉树,两者相辅相成。
Treap树的每个节点都自带一个随机值,他们符合大根堆的性质。
split通过将原树分为L,R两颗树来实现分离,实现过程具体大概是沿着比目标值key大或者比它小的这一条线进行递归,将比它小的分支接入L,比它大的分支接入R。
1 | void split(node *&t,int key,node *&l,node *&r) |
merge则是通过随机数的比较进行恢复大根堆,最终结果是一个Treap树,并且具有平衡二叉树的性质。
通过大根堆随机数来维护平衡,merge通过大根堆进行恢复,这两个函数是Treap的核心,都是平均logN的神仙算法。
1 | void merge(node *&t,node *l,node *r) |
一种Insert的思路是:将插入的节点看作一个树,先通过split把原树分成比它值大的一棵树和比它值小的一棵树,然后将插入节点merge到其中一颗树上,最后两棵树merge达到insert的作用,O(logN)
一种erase的思路是:将原树split成三颗树,其中一颗仅有要删除的节点一个节点,最后merge其余两颗树,O(logN)
1 | void insert(node *&root,int val) |
原核心代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18void split (pitem t, int key, pitem & l, pitem & r) {
if (!t)
l = r = NULL;
else if (key < t->key)
split (t->l, key, l, t->l), r = t;
else
split (t->r, key, t->r, r), l = t;
}
void merge (pitem & t, pitem l, pitem r) {
if (!l || !r)
t = l ? l : r;
else if (l->prior > r->prior)
merge (l->r, l->r, r), t = l;
else
merge (r->l, l, r->l), t = r;
}
实践代码:
1 | #include<bits/stdc++.h> |
不多描述了,本人还没完全熟练
Treap代码存档 https://cp-algorithms.com/data_structures/treap.html
哈哈,跟风来一个2018总结流水账
2018也算是充实的一年了吧,一年之前的我是这个图里这样的哈哈
想不到一年之前还在被线代逼到命运角落的小伙子,现在已经轮到被概率论逼到自闭了
(哈哈哈并不好笑)
这一年,我真的变了很多,去年这个时候,我还沉迷在DNF中,一周7天想的都是啥时候去开团,想不到短短一年就变得不那么想碰游戏了。
去年我立下了一个flag,2018要变成一个外向跳脱的人,那时候群里的人还笑说说你要是外向了那我们怎么办,可是现在我确实洒脱了很多。
…或许是因为真的有很多我的朋友都有这样的阳光的特质吧,所以才会一次一次地在心情沉没的时候被路过的他们捞起来,这些朋友会是我一生的宝藏。
不知道现在算不算达到了这个目标,希望变得外向的初衷,是希望自己能更好的处理所有的事情,无论是学业还是生活,寻找到一个平衡点,让自己感觉到自己还在活着,而不是奔波在学业上失去了生活的目标或者整天混吃等死失去了人生的意义(等等,我现在就是这样啊)
如果非要说完成什么目标的话,还真没有,因为18的上半年忙着分流,而下半年刚接触到专业内容,那个时候说要有什么目标估计都是说笑的,不是有那么一句话么,那些十几二十岁就决定好自己人生的人,其实什么都不明白,未来要自己一步一步去摸索出来,能留给计划的其实不多,但却足够你的即兴发挥。
这一年认识了很多人,很多大佬,更多的巨佬,他们都在自己定下的路上前进着,这让我也得以窥见适合我又或是有可能适合我的那一条道路,感受到了ACMer的严格的自我要求,看见了开源人运用自如那些写的十分精妙的开源代码,见到了信息安全那种通过无数坚实基础堆积而成的技术,见识了计算机科研的一点精研不松劲,也注意了那些平时住在图书馆的绩点大佬。是啊,路太多了,不知道哪条路适合,但也不想纠结,那就顺其自然吧,keep一颗观察的心,愿命运把我带去我该去的地方。
(怎么说着说着就沉重了起来,哈哈)
(怎么写了这么多字了)
(哇已经凌晨4点了)
(不慌不慌码完再说反正明天元旦假)
那接下来还有什么呢?
哦对了,先推一波这个503OJ,这个挺好玩的,是用QDUOJ的开源代码搭的,有兴趣的可以去看看。我还搞了个windows安装包(其实就是个定了地址的浏览器),真的很好玩。
接下来说下其他的吧…emmm2018错过了一个女孩,算是一个遗憾,算是我的原因吧,暂时不想在这谈这个了,徒增烦恼。
以前不常做复盘,今天一做复盘才发现自己原来已经经历了这么多事了,时间也快到天亮了,但还好像是有很多东西没说到,又或是已经遗忘在了时间长河里。
美好的回忆也好,开心的时刻也好,一些遗憾也好,马上都将随这日历划入2018的旧时光,现在还有点遗憾的是原本准备找画师小姐姐在2019前给画个专属头像的,小姐姐好像有点事情就没办法了呀。
要变的更稳重,不止是外向,而是要洒脱,年轻的心,好奇的心,观察的心,永不停止学习的心,而不止于畏缩外界的强压,我希望有这些赤子之心,我希望变成一个有这样心态的人,我期盼着更有活力的明天。
我要感谢朋友们的陪伴,特别是那些在我低谷之时伸出援手的朋友,还有那些让我认识到世界有多宽广的朋友,大家都要完成自己的新年目标啊。
2019—要变得更厉害啊!
F.R.
2018.12.31凌晨