2025小猿暑期封闭营记录

## Day 1
参加入营测试，搞了154分，rk1，虽然一题没做对。

T1 我写了暴力24tps。正解其实就是预处理质数，然后枚举每个质因数的个数，顺便处理答案。值得注意的是：要想数尽量小且因数多，质因数的指数一定是降序的。小技巧：注意两数相乘大于另一个数的判断中可能会出现爆long long的情况，所以尽量换成除法。

T2 模拟而已，虽然正解是并查集，我少考虑了一种组合方式，所以90pts。

T3 模拟而已。忘记考虑图不连通了。

T4 太骚了还是不会。

## Day 2
回学校拿毕业资料了。中午出去爽吃了一顿。下午懒得回来，和朋友在国贸逛街打游戏了一下午。喝了两杯奶茶晚上窜了，可能中午吃的是日料，有点影响吧。

## Day 3
位运算专题。

T1~3 水，不多说了。

T4 海明码，我想找规律，但是后面发现暴力能过。启示：要注意数据范围。

T5 二进制与一 II,恶心了我好久。之前在洛谷比赛的时候就做到了，当时想了很久，赛后也调试了很久，发现思路根本不对，放弃了。结果在这又遇到！其实就是对于答案的两种贡献方式进行枚举+一点点贪心。需要一些编码功底的。

T7 动物园。没开long long见祖宗！

T9  小奔关闹钟。忘记考虑自环，加上编码混乱，就裂开了。

T6、T8 还是不会。

## Day 4
思维好题专题。

T1、T4、T6 水，不多说了。

T2 两人过河。最快的一组接或者最快的一个人接，处理剩下三个及以下的情况。

T3 GZ24奇偶异或。个人认为最牛逼的题，很多思路可以解。  
1. 设 $m=2^n-1$ 所以 $m-k=m \oplus k$
2. 因为 $A \oplus A=0$ 所以构造异或和为 $0$ 的序列，所以他们奇偶位的异或就相同。虽然我不知道怎么证明的lol。

T5 倒水。思考的关键是杯内的水如果有的低于桶内的，有的高于桶内的，那就永远无法一样，会无线接近于桶内水的温度。

T7 没看。

## Day 5
上午讲了比赛注意事项，下午搞了知识竞赛。

比较蠢的安排。

注意事项发一篇博客下来读一下就行了，没必要专门讲还全屏吧。

知识竞赛，让我想到一个梗：“镜堂班=竞唐班" 。比较无聊。显得这个集训不怎么专业和严肃了。

## Day 6
数据结构专题树1专题。

T1 贪婪大陆。非常巧妙的用两个树状数组进行了动态差分。

T2 统计和。类似线段树模板，又让我复习了一遍线段树，这下忘不掉了。
>《线段树之歌》  
线段树，真奇妙，区间操作效率高  
定节点，含两值，sum 存和 tag 标记  
左儿子，ls 来表，x<<1 就得到  
右儿子，rs 不难，x<<1 再或 1  
push_up，父节点，左右之和来相连  
push_down，要注意，标记下放别忘记
若标记，不为零，左右儿子均继承  
算长度，分两半，各自加上对应值  
父标记，要清零，免得下次出差错  
build 函数，建线段，递归下去到叶端  
叶节点，sum 初置，tag 为零要牢记  
左右建完上推值，整树构建就完成  
update，改区间，先看是否全包全  
若是则，改 sum 加 tag，直接返回不用怕  
若不全，先把标记下，再分左右去更新  
更新完，上推值，保证父节点正确
query 时，查区间，同样先看包不全  
全包则，返回 sum 值，无需再往下面去  
若不全，标记先下放，左右查询再相加  
最后返回总结果，区间查询就完成  
主函数，读输入，n 和 w 要先确定  
build 一下初始化，然后处理 w 次令  
x 是更新点，a 位置加 b 值  
y 是查询段，a 到 b 和输出  
线段树，要记牢，push_up 和   down 很重要  
递归思想心中藏，区间操作不慌张  
记此诗，常回想，代码写出不迷茫

T3 树的分解。历遍这个树，搞到 k 个就截断，搞不完就不行，搞得完就行。

T4 正解字典树，实则 map 过。

T5、T6 生日和色板游戏差不多，状态压缩线段树。生日哪个sb出的题面，和老奶奶说梦话差不多。

T7 主席树，主席还是太持久了，以后再学。

## Day 7
出录取结果了，靠编程靠进莞中镜堂班，太爽了，裸分甚至上不了莞中。

下午搞注册啥的。

## Day 8
模拟赛搞了57分，进厂了。

T1 小w的铁路图，暴力挂了。正解是dij $n$ 次找最短路和次短路（不经过特点边）。

T2 树的覆盖，我依然写暴力。实际上是树上DP，非常复杂，后面我要恶补树上DP。   
学到一个小技巧：定义一个临时数组，降维，降低编码量，提高可读性。

T3 靶向药物治疗，恶心的基环树，以后有空专门学。

T4 不会。

## Day 9
树与树型dp专题。

T1、T2 水。

T4 SAC E#1 - 一道难题 Tree，当时想的不是很明白，比较抽象的模型。实际就是看在这里剪开合适还是在子树剪开合适。  
树形DP的通用搞法就是历遍一个子树就处理一下。

正在渲染内容...