SDSC2021 游记
SD summer camp!
首先吐槽一句“数据结构提高班”只讲一天数据结构，“高级算法班”讲了线段树、平衡树、分块等等一堆数据结构。。。
7.15 报道
大老远坐车到日照，花了整整一上午时间 QAQ。在车站坐公交车去山外，山外在最后一站，一路上一直在听歌。为了防止耳机没电就用的有线耳机。
报道时就已经有好多人了，官方没说明白路线，在学校里转了好久才找到报到处。拿到学员证（fan ka）后知道了我在新8号楼，结果这是唯一没有桌子和wifi的宿舍楼、、(╬▔皿▔)╯。还有一些没什么用的信息。
在宿舍知道我市还有教练带队来的初中生，xxs，没有高中的。认识了来自德州的准高一学生zqr，这家伙还会网络流 orz。
去超市买了可乐和阿萨姆，，，，这一晚上大概就是玩。
7.16 day01
山外的空调好冷 ≡(▔﹏▔)≡，开的16度但是晚上被冻醒好几次，早晨常规6点起床了，早饭吃到了山外最喜欢的豆角。。几乎每天每顿都有。
今天上午在报告厅上课，由来自莱州一中的 孙名媛 孙铭远讲述图论相关知识。
先讲了 dijkstra 以及堆优化与桶优化与次短路问题及其证明，有个大佬说可以用 A star 搞。。好吧我不会 A star。
然后就讲了用 A star 的 K 短路问题，很多人不那么理解估价函数，我大概明白了，然鹅我还是不会实现。
还有已经死掉的某算法以及 Floyd 与 johnson
接着是最长路问题，没啥好说的，然后下课了。
这里有一个小插曲：报告厅在-1楼没有厕所，我们只能去楼上找了一个位置奇怪的厕所。。。然而那里只有两个位置，等着的却又很多人。有人说“这和排队接水是一样的” “你怎么知道每个人用的时间？” “估价函数！” 简直笑死。。后来知道正经的厕所在六楼。
上课后讲了差分约数系统，大概就是一堆不等式的操作，，并且讲述了虚拟原点的作用。
然后是生成树相关。先介绍了两种常规MST算法与很有意思的 boruvka 算法，然后讲述了最小瓶颈路/树和次小生成树。
随后详细讲了 kruskal 重构树及其优美性质，今天的课程就结束了。
各路大佬简直吊打我
下午自己随便切了几道题目，这段时间的题目会在夏令营结束后选几题单独讲一下。吃完晚饭去机房，然而人却满了，，，有两个组的用同几间机房，白天上机时间错开，但是晚上就不行了。这一点很不满意 (* ￣︿￣)
截至7.18 23:00，我晚上没有在机房抢到一个位置。
所以我和朋友在宿舍用热点切题去了~
7.17 day02
今天早上起晚了一点，，
依然是孙名媛讲述图论。
先讲了欧拉回路的定义、性质、美妙性质以及运用。
在讲 CF547D 的时候，“找到一条欧拉回路并对边定向” 没有讲述过程，后面做这题的时候直接去世。
然后是树上相关问题。
括号序，欧拉序，dfs 序。
还有重链剖分。
我在十几天钱看过树上相关问题，对于这种在树上一顿dfs与bfs理解起来还是没有压力的。后面说树链剖分一般和数据结构同时出现（其实基本都是线段树），我 /(ㄒoㄒ)/~~
一个多月前我还会写线段树板子，现在已经忘得差不多了。前几天k神给我一道线段树优化 dp，我连读题的心都无了。。。
最后是 dsu on tree，也叫树上启发式合并。是一种基于重链剖分，合并重复扫描，从而降低复杂度的算法。也没啥复杂的，还是树上操作，实质上是一种 暴力，但不完全暴力 的算法。
在最后的最后，甚至还提到了点分治。。真要讲了那真的是 “数据结构提高班”了。
朋友在山外超商里买了一个耳机，花了几十元（忘了。。），同款的在某宝只要个位数就能买到（）。
认识了来自青岛平度的准高一学生官同学和与他玩mc的小朋友。他的 linux 技术实在是太强了 orz。我连 wsl 都不会用 ╥﹏╥...
下午举行了 %你赛 形式的练习
T1：次短路 T2：差分约束系统 T3：欧拉路径 T4：使用重链剖分求LCA T5：dsu on tree的课件例题 T6：dsu on tree简单习题
t1、t4我之前做过。t2是小k的农场，机房有大佬发现直接输出 Yes 可以得85分，还能下载数据。所以他们共同合作，特判数据，得到了比我快4s的速度。t3能想明白，但最后的实现上出了问题，，对边定向到底是个什么操作啊。
smy发了t5的标程（因为讲课时很多人都没听懂，就算懂了也不会实现），t6只要把t5的板子改一下就行了。
这个班是选手讲课的下界，往下的班就是教练上课了，但是没有真正意义上的%你赛，上机时还没人盯着 (￣y▽,￣)╭
晚上听了yamf的讲座，讲述他羟基进pku的事情，我在下面玩游戏，大概听了半个多小时就回宿舍了。
7.18 day03
早上室内温度又低的离谱，室内比空调制冷的温度还低。
今天是yamf的数论课，但实际上讲得很少，从最基础的质数开始，最后连exgcd和欧拉函数都没有讲到。
下午的练习
T1：分解质因数
T2：线性筛质数
T3：GCD&LCM
T4：进制转换
T5：同余
T6：乘法逆元
t1、t2做过了。t3是gcd和lcm一顿推，最终推出简化的式子。t5开桶统计，t6卡掉了我的费马小定理，，
唯独t4要单独说一下，九连环
这道题实质上是一个递推求方案数的题（为什么写进制转换？），但是没有取模，不写高精最终只有30pts。
然而同机房的神仙发现，用python可以直接水过去，只跑了不到200ms！
所以我不要脸地去Trick了。 <(＿ ＿)>
晚上是lyh的金牌之路，我听完了，但是大部分时间还是划水。
想不到lyh也玩 \(osu!\)
所以我一边听一边玩。
听完讲座后去超商买了零食。
还有好多琐事忘了。
7.19 day04
今日的课程可就友好太多了，基础算法，还是yamf。
yamf：今天的课程一定很轻松的~
然后他讲了鱼神出的 【XR-1】逛森林
好多人都没听懂，我当时在打电动，没有听完 QwQ。
yamf：这题没什么思维难度，就是实现起来比较麻烦。
还有二分，st表，倍增，倍增LCA，当然这些没啥好讲的，主要是讲题。
yamf说他把洛谷账号注销了，除了洛谷独占的题目，别的都是从loj之类的网站找的。
练习
T1：bfs
T2：RMQ（ST表）
T3：倍增优化数据结构
T4：使用倍增求LCA
T5：二分答案的课件例题
T6：二分答案简单习题
只有t2做过QAQ
t3是 [SCOI2016]萌萌哒 ，这题我自己想了好久，然而没有想到正解。正解是st表+魔改的并查集。
t6 RC Kaboom Show 是一道纯英文的CF题目，首先题面我就没看懂，还有一个类似于扫描线的过程。。。最后放弃了。但是洛谷唯一一篇题解是lyh写的诶~
晚上的讲座有变动，我没去。
高级算法班的同学们模拟赛出了三道题，分治，数学和lxl题。zqr只有50pts（
_rqy：题目太水了
7.20 day05
我们最爱的 \(lxl\) 来啦！
lxl：你们这里好热 orz
lxl讲了树状数组，线段树，单调队列，堆啥的，还有一些题 （线段树讲得很浅，用的还是以前的课件，讲得和洛谷五一课几乎一样，然而这并不影响我们对lxl的热♂情）。
最后还有STL演示！
map < string , string > p1;
map < int , int > p2;
p1 [ "CCF" ] = "发财";
p1 [ "lxl" ] = "良心出题人";
p2 [ -1 ] = 114514;
lxl懒得搞练习题，所以下午自己切题了。
晚上是smy的dp讲座。
我究极绿宝石一周目通啦！
也就是在这一晚，我玩 \(OSU!\) 时笔记本电脑突然卡住，关机重启之后x键就失灵了。。
在超商买了一盒某巢咖啡。
QWQ
7.21 day06
真是有意思的一天。
今天是lyh的dp课。
但是这个dp课啊，，，
从数字三角形开始讲，，，
是怕有人听不懂还是单纯的水时长啊 (#｀-_ゝ-)
线性dp，背包，区间dp，树形dp，数位dp，状压dp，单调队列优化（有人说不会单调队列，所有又讲了一遍，水了半小时）。
每一样都讲了，但是每一样都讲得不是很多，没有讲很多题。
课件一共讲 40+ 页，但是一共有一百多张。
最想吐槽的是树形dp。
例题只有没有上司的舞会和选课。
练习
T1 线性dp
T2 区间dp
T3/T4：背包（并不是那么显然，可能需要一些思考） T5/T6：树形dp
六道题我做过4道。。
估计某位yba神仙也是，然后直接提交上去了，瞬间400，rk1。
我直接做没做过的题了。
T4 垃圾（我）陷阱
显然地，是背包，只不过状态的设计花了我亿点时间。
T5 “访问”美术馆
背包属性dp，最难的地方在于读入和建树。
T5/T6 都是树形背包dp。
没有做状压dp的题，我不是很喜欢这种复杂度奇高，接近于暴搜的dp。
树形dp就很不错啊。
状态设计与转移都很优美，复杂度低，在各种树上问题都能用到，还有很多套路题可以水AC数和题解（
树形dp水题和基环树有点氵的题（因为我一开始的思路错了。。）
又去了超商。
7.22 day07
今天凌晨0:00，我去隔壁宿舍吃零食。
有个人让我和他们玩三国杀，我就和他们开了一把。
我的角色牌很垃圾，最后选了界吕蒙。
就没有然后了 ≡(▔﹏▔)≡
被管理员查水表了 QAQ
还做了半个小时的蹲姿 啊啊啊。
然而早上起来一点都不疼，就是特别困。
上午讲得dp优化，基本没在听。
单调队列优化，数据结构优化，斜率优化，杂题选讲。
斜率优化只听了个大概，不会推式子。
下午一点就去练习
T1：数位dp T2/T3：状压dp T4：二分+单调队列优化 T5/T6：斜率优化
做得很慢，而且除了 T4 都是看着题解做的。
被各路神仙吊打。
好吧。 ╮(╯-╰)╭
就这样结束了。
大概明天会就这段时间的题目水几篇题解。
走出机房时，正循环播放着ホタライズ -2015 Summer Edition-。闷在耳机里阵阵电吉他声，将刺眼的夕阳染上橘黄色。
我大步穿行于熙熙攘攘的人群，仿佛自己也成为了他们中的一员。
仅仅是七天，但似乎不再孑然一身了啊。