2023 Oct. Week-3 Summary

2023.10.16 - 2023.10.22 （椰树牌椰汁！）

学习内容

学了
- 搜索
  - DFS，剪枝优化
  - 折半搜索（调整折半常数优化
  - k 短路（A*）
  - 迭代加深（IDDFS）
- 大量模板
如学（需要复习 / 做题）
- 数据结构
  - 回滚莫队，二次离线
- 动态规划（多做题
  - 换根 D P
  - 更抽象的优化方法（wqs分治，矩阵神法
- 网络流
  - 二分图等问题的网络流解法
  - H L P P
- 平衡树
  - 文艺平衡树（翻转等 Tag 使用）
新建文件夹（要学了要学了
- 线段树加强
  
  线段树合并、分裂
  
  猫树、主席树
- Balanced Tree Plus
  - 替罪羊树
  - 红黑树（对思想进行一个理解）
  - pb_ds 的尝试与使用
- 随机化、离散化算法
  - 爬山
  - 模拟退火

总结部分

四天的 lxs Contest，怪

感觉这周其实状态还行，但是复赛 GG，还是基础太菜

10.16 Day1

Trush Round，完全不会...

T3 靠靠猜高概率 \(N - 1\) 水了 60，感谢 Mea 没绑 Sub
10.17 Day2

差异化明显，T1 巨大水题，据说蓝桥杯某年原题（数字三角形？

然后很傻的觉得 DFS + 超出 Sum 剪枝过不了

于是小测一下，发现 \(N <= 11 ~|| ~A[1] <= 5\) 时暴力可以卡过

于是果断打了 \(A[1] > 5\) 时的表，只有 26 KB，塞下了！

但浪费巨大时间... 好在成功卡过

T2 不会 DP，不可做，果断放弃（后面讲题的时候居然是五维暴力做法，我？？？？）

T3 赛时糊出来了！又没写完... 考虑到先 \(BFS\) 预处理连通块。

显然不同连通块之间互相不可达，同一连通块内从最左端 \(BFS\) 处理 \(Dis\) 。

则两点间实际距离与其 \(Dis\) 的差为 \(0\) 或 \(2\) 。

起点终点同行时分讨起点后第一个障碍所在行与起点所在行相同或相异即可。

不同行时可以放到同行情况下 \(+1\) 或 \(-1\) 即可

评讲时讲的按每个障碍物分块，觉乎可行，好像也本质相同

当时晚饭又糊了一种做法，用 \(BFS\) 预处理每个连通块内一条唯一的 主路径

然后考虑任意一点到 主路径 的距离不超过 \(1\)，然后分讨，感觉挺简单

（但好像回寝后细想觉得分讨难度还是很大，遂弃

T4 没看，后面看了和 \(xing\_yu\) 讨论了题意，还是没理解
10.18 Day3 想象学竞赛专场！

T1 OI测试题，不开快读会 GG，实测正常 \(getchar\) \(600~ms\) 左右，\(fread\) 轻松 \(200~ms\) YYDS ！

核心是一个并查集，将道路和询问都按照权值 从小到大排序。

每次将道路插入并查集，处理对应权值的询问（是否在一个并查集内）即可

顺便研究了不同算法下 并查集 的速度

记住：只采用路径压缩的均摊复杂度是线性的！（用 K 级二项树卡到 \(log\)）

朴素合并 + 路径压缩记时间为 \(100 \%\)

按 \(Size\) 合并 + 路径压缩 \(75\%\)

按秩合并 + 路径压缩 \(78\%\)

按秩合并 + 暴力查询！\(91\%\)

确实一般情况下只写路径压缩是够用的 ~

T2 想象学巅峰，全机房两小时没看懂样例！

然后 %%% \(xing\_yu\) 成功用 OEIS 算法找到规律！

最后我直接强行口胡了一波 感性理解 被接受力（喜

附上简要题意（解？

定义一堆石子的 “内容” 代表之前已合并进这堆石子的石子集合
例如进行 (1, 2) （2 合并到 1）操作后，可以认为 1 的 “内容” 是

当结果和中间值互不影响这句话
可以理解为
任意时刻相同编号的堆中内容相同
考虑当 N = 3
合法的不同序列即有
#1 (1, 2), (1, 3) //第一步后，内容为 {1, 2} 的堆编号为 1
#2 (2, 1), (2, 3) //第一步后，内容为 {1, 2} 的堆编号为 2
#3 (2, 3), (2, 1) //第一步后，内容为 {2, 3} 的堆编号为 2
#4 (3, 2), (3, 1) //第一步后，内容为 {2, 3} 的堆编号为 3

#5 (1, 2), (3, 1) //第一步与 #1 相同，但第二步后，内容为 {1, 2, 3} 的堆编号为 3
#6 (2, 1), (3, 2) //第一步与 #2 相同，但第二步后，内容为 {1, 2, 3} 的堆编号为 3
#7 (2, 3), (1, 2) //第一步与 #2 相同，但第二步后，内容为 {1, 2, 3} 的堆编号为 1
#8 (3, 2), (1, 3) //第一步与 #3 相同，但第二步后，内容为 {1, 2, 3} 的堆编号为 1

故而可以尝试倒过来看，从最终的一堆开始划分成 N 堆
每种不同的划分一定能保证题目所给性质
于是原题可以看作将 N + 2 边形划分成 N 个三角形
于是想到卡特兰数，并发现每次合并的时候顺序可以不同
一共 N - 1 次划分，所以最终答案是 C(N) * 2^(N - 1)

T3 想象规律题，会结论就可以直接做了

结论 : \(N\) 个元素的 \(M\) 重子集个数是 \((M + 1)^ N\)

（~~很好找规律，使我的草稿旋转，爱来自zhicheng~~

T4 串串 （DNF

然后大家钦定了 S2 不考串串，然后...

T2小挂，T4大挂，赛后改了。但赛时拿了 256，赢！
10.19 Day4 想象学原题

赛前 zhicheng 远洋顶针，鉴定 T3 为原题，被制裁了（好像最后 zhicheng 还挂了 20，输！

T1 卡住 15 min，然后物质团区间和可以转化为前缀和两点差。

然后求前缀和，排序，检查差最小值，维护同差最大长度，End

T2 又是规律题，先跳的，开了 T3，写完回来推推，考虑一个节点的左右子树节点数

顺便想想节点数分别为 \(0， 1， 2， 3， 4\) 的情况数 \(1， 1， 2， 5， 14\) 嘶

昨天考了今天又来是吧，然后分治 + 卡特兰数，结束

T3 原题，Luogu Problem a 复习一遍做法

T4 又是串串，略了略了
10.20 Day5 模板大赛

上午一直在调一道搜索，下午只把前面的一些题打掉了... 当时就感觉还是不够熟练。

后面也有部分板子不会的... 只能钦定不考
10.21 游寄部分总结

去的时候感觉还是紧张的，从学校出发之前还提醒了 \(Klein\) 带准考证。

然后到了高新发现 自己没带，抽象。

进场前看到了一些同学... 交流，发现自己好像很蒻，自闭

拿到题先通览一遍，T1一开始没看出来，T2 感觉像个 DP，但是 \(N~log~N\) 的复杂度确实...

T3 巨大模拟，当时感觉应该好拿一些分。T4也没有 idea

决定正序开题，想到 T1 的小数据范围，似乎可以暴力，速写，但是调了好一会儿

看了一下 T2，不是很会正解的样子，想到 \(N ^ 2\) 的暴力，写。

测 \(800\) 的样例，\(WA\) 了？！比较诡异... 当时心态就不太好了，直接过了去看 T3

为了好调，直接分了四个函数进行一个写，40 分钟过掉了前两个样例，感觉还好

然后被大样例薄纱，一直没调出来。当时觉得 T2，T3 正确性都问题，已经无了

心态很慌... 强制把 T3 大样例第一个定义手玩了一遍也不理解

（实际上当时对题意理解有问题...

应该是结构体内每个基本类型都要分别对齐，我想成只满足结构体的最大对齐要求就行

然后直到离场都没有调出来，考完速问了 \(zhicheng\) ，瞬间理解，然后裂开

当时考完出来就感觉只有 \(100~pts\) 保底，啊，慌，回家测了 T2 正确性居然没问题，怪

（甚至第二天问了 \(zhicheng\) 原样例，好像和我程序输出是一样的... 不知道场上到底看到了什么

倒是 T3 挂到只有 \(5~pts\) ，没了...
总结来说
- 首要的还是基础问题，考前模板大赛很多模板都不熟甚至不会，这就使前期不管是听课还是补题，联考都比较艰难，效率也很低，准备在 \(NOIp\) 前用晚自习部分时间和回寝时间把《算法竞赛》 上内容过一遍。
- 其次是心态和策略，考试的当天其实状态是不对的，可能是想强制自己不那么紧张，一路上都在发披风，反而最后更是乱掉，出现了 准考证没带 这种智障问题。开题后也没有及时调整，前两题打完后就在和 T3 死磕，题意理解也不到位，不够仔细，相对失败。
- 最后是平时的状态，其实个人感觉主要还是开学，从初中的全科学习转到竞赛上，始终没能把握准学习节奏，也没有完全摸清自己的学习，做题效率究竟如何。导致制定了计划却常常完不成，经常觉得时间不够用。或说在有些板块的学习倾向性过高，不够全面，有些板块可能还行而部分板块可能板子都不会写。这也是以前的学习不够系统性导致的。到考试前两周感觉计划的完成率有所提高，但其实总体效率还是较低，有很大的进步空间。

近期计划

总体
- 强制要求难题，新学的要写题解或总结，可以少做题，但应该把每道题尽量摸清楚，不应出现一个类型做了几道但见到显然的同类型题一点反应都没有的情形，也不该出现原题完全忘了的情况。联考的总结也需要跟进，不管大考小考，同样对待才可能有同样收获。
- 减少畏难情绪，突破不擅长而且常考的板块，诸如 DP 这种如如东西，从来没有吃得很透，做了部分题但见到新题还是不够明晰，难以想出思路，需要更多的练习和总结
- 补全基础知识，保证掌握的知识点较为全面，不应有太多缺漏，也有助于对课件以及联考题解的理解。
详细计划（初