2020暑假SSL集训の总结
这次集训共分两部分：
~下午 共四天 然后放一个几天的真正意义上的暑假……
然后是~ 共天 (晚上半天一天 我可是掰着手指数的……)
总的来说 这天学了很多很多东西 之前纪中模拟赛打了几个月 但其实算法啥的没有新讲什么 还是感谢这次集训让我学到了很多知识点与算法.
~
第一个学的是哈希表 总的来说还算掌握 但哈希也只能算是一个小工具 一般要和别的算法结合使用 自身不能说是一个算法吧
然后就学了并查集 之前觉得这东西好难好高级 结果
(就这？？？¿ ¿ ¿ )
感觉并查集也算是比较掌握的一个算法吧…… 更妙的是：
学了并查集 可以用来写最小生成树 真是一石二鸟 一箭双雕 一虎杀两羊 一举两得啊！！
最后就是学了关于区间的算法：离散化&线段树
离散化 可以处理数据比较小的区间问题 但其实它是用来压缩空间的……
线段树 一种高效的求区间问题的数据结构 现在看来还是比较好理解的 当时讲的时候感觉就是懵懵懂懂 代码量还是比较大的 还可以用懒标记来优化 让你的线段树速度起飞 可惜的上没介绍 这是自学的
就不透露了 反正是回老家和去旅游……
(啊我又暴露了)
~
回来就学了单调队列 就是字面意思：
一个严格递增或递减的队列
这玩意一般就是求某个范围内的最值(这算) 以及什么最大子树和之类的 还可以用它来优化
然后是单调栈 还是字面意思：
一个严格递增或递减的栈
求的是的左边第一个比大的或第一个比小的数 或坐标……
你可能觉得：就这就这 我大 不能做？还是的r_ r_不行了？
其实 单调栈的查询是的……
然后学的东西就奇怪了起来：
树形：在树上做 所以说是个图的东西……
甚至还要搞邻接表 还要双向？？宁是最短路还是生成树呀？
要搜索树 递归 但是由于它是个递归 有传递性 所以动态能量转移方程也好推一点 但它相当于一个图论树形结构
拓扑排序 这个算法还比较友好
先统计所有节点的入度 对于入度为的节点就可以分离出来 然后把这个节点指向的节点的入度减 一直操作 直到所有的节点都被分离出来 但一般也不会裸着 要结合求解
树状数组 个人感觉挺实用的 代码量少 基本那些不毒瘤的区间问题都可以用 记住几个基础操作函数即可……
然后就是最的东西：状压
它的数据很小很小 可以根据此判断 一般求的是一个地图里……放 ……条件的方案数 其实它就是暴力枚举 几重循环都有可能 但它用的是位运算判断 用 判断能否放
最后几天学了名字高级 但很简单的东西：二分图
理论啥的学长讲得晦涩难懂 代码很简单 也好理解 其实只用记住一个最大匹配模板 其他的都是根据最大匹配做的 说一般是和其他算法一起用的……
后面又学了一个求的算法 表
这种也是记住一些基本操作 其他的就看题意了
表也涉及到位运算 还是要好好理解……
最后 学了 即求最近公共祖先 久仰此名
因为也只能单纯的求最近公共祖先 所以也基本是模板
预处理 查询 连边 调用 基本就是这操作流程
所以应该也是和其他算法结合使用吧……
后面两天就是跟着初三高中打模拟赛 爽快滚粗
还是学到了很多解题思路的 以及比赛策略%%%
以下为集训事纪：
(时间轴顺序)
刚刚考完期末 大家都在对成绩……
我旁边的奆爷考了(应该)是年纪第一 机房其他人好像也成绩很好的亚子……我只能当场去式 自闭
将升初一的来机房了 仿佛看到了当年的自己……
因为有人中午在机房偷腐 很生气 罚了除了我和大爷以及女生之外其他人款 以及要他们写检讨(还有人发到水博客？？)
日左右 王者世界冠军杯总决赛 以及总决赛 (这能不看？ )
日左右 良心发现请全机房吃 还用的是罚款的钱我笑了
日早上我打一个什么深圳的若智比赛 题目很水很水的 那天早上新高一来报道开始军训 在此希望人没事
日当天傍晚陈博 全屏爽腐站 还带耳机 当场被抓腐 日下午直接回家 变相提前放假真爽 晚上AJ还叫我们年级到办公室讲道理讲了一个小时 白给一个晚上……
好像这一天学长也走了 他教了我们一个月的算法知识 很感激 可惜他要退役 以后可能都见不到了 也没有拍照留念 算一个遗憾吧……
日下午 奆爷因为要带新初一的学弟学妹所以提前走了 最后坐我旁边嘻嘻哈哈 晚上就改模拟赛的题+随便搞搞洛谷模板题
日他们那些学前助理去报到了 不知道新初一什么时候去报到……下午也是在洛谷上刷刷水 蓝题啥的 让我们拍了一张合照 就要离开了 很平淡地离开 好像也没有人告别 几天的集训就很自然的结束了……
集训让我收获了非常多知识 虽然它缩短了我们假期很多时间 但是与其在家颓 还不如多学点东西 不过 我的暑假作业还只字未动???????????? 以及初二了 要好好搞生地 尽量把文化课搞好吧
集训20天打了86+篇博客 算是一个不小的突破吧……(后面还要补几篇)