动态

上午模拟赛，打得一般(110，rnk44/66)。四道题全是计数题。
- T1(100) 用并查集切+计算切了
- T2(0) ~~什么叫我不会写暴力？~~
- T3(0) 暴力炸了，特判 subtask 计算错了没分
- T4(10) 交了个暴力。不会推式子。注意力惊人的1人场切。
晚上讲莫队，分块。终于有点熟悉的了。

2026-07-22

7.22外出集训总结

上午几乎听不懂的计数专题
- 题目难度几乎都是黑，少量紫……在讲题下过了俩？
- 还有不仅式子难推还有几百行实现的猎奇题目qwq
晚上
- 点双、边双讲题

进度条过半了吗这是

2026-07-21

7.21外出集训总结

上午NOIP模拟赛(155,rnk58/65)
- T1(0) 素数筛预处理本来欧拉筛能过的，调代码的时候发现结果不对，改了两下（其实原因不在这里，但是改了莫名就对了，导致合数被筛了多次）在本地运行时间依然正常，结果交上去判题机全TLE了。
- T2(100) 单调栈板子
- T3(0) 换根DP。暴力喜提零分。
  - 思路是把LCA的和转换为记贡献，即每个节点是多少个节点对的LCA，乘上自己的id。
  - 于是 $cnt_u = sz_u^2 - sum(sz_v^2)$ ，节点贡献即 $cnt_u*u$ 。
  - 先用一次以 $1$ 为根的 DFS1 算出来每个结点的 $sz$ 和以 $1$ 为根的 $ans_1$ 。
  - 再跑 DFS2 进行换根运算
  - 把根从 $u$ 换成 $v$ 即：
```
int b=n-a;
int delta=(v-u)*2*a*b;
int now=cur+delta;
sz[u]=b,sz[v]=n;
dfs2(v,u,now);
sz[u]=n,sz[v]=a;
```
- T4(55) 预处理最长公共前缀 $lcp$ ，计算对于每个 $i$ 位置，左侧的双块个数 $lcnt_i$ 和右侧的 $rcnt_i$ ，相乘计数得到答案
晚上会讲强连通分量相关内容

2026-07-21

卧槽素数筛预处理TLE了？！本地跑毒瘤数据都在时限内，交上去全炸。猎奇评测机。

不过我这个写法对于合数多标记了不少次……确实有问题……可更猎奇的是我原来写的没问题，后来改了一下就废了。

255 成了 155 qwq

喜提最近模拟赛最烂排名（这次题目简单，居然有12个人AK……）

2026-07-20

7.20外出集训总结

上午是数论专题，讲了一些数论基础、迪利克雷卷积、欧拉函数、莫比乌斯函数等……这部分真的……听不懂
下午做上午的题
晚上接着讲树，更多是树直径性质的运用

2026-07-20

数论好可怕。听不懂。

2026-07-19

7.19外出集训总结

周日放个小假
之后出去玩了，逛了下中大大学城校区、吃了顿火锅、逛了下广东省科学中心。
然后 16:00 返校了。
晚上是讲了一些关于树的性质（如重心、直径、LCA之类）的内容。

2026-07-18

7.18外出集训总结

上午：NOIP模拟赛(100,rnk26/57)
- T1(100) 用不对劲的复杂度（最好 $O(nlogn)$ $O (n l o g n)$ 最坏 $O(n^2)$ $O (n^{2})$ 的时间复杂度）过掉了 $1\leq n \leq 10^5$ $1 \leq n \leq 1 0^{5}$ 的数据
  - 正解可用单调栈。我这个算是狗屎运。
- T2(0) 递推式没想出来 CF581E
- T3(0) 性质分析方向错了…… JOISC2022D1T1
- T4(0) 环 $\Rightarrow$ 性质分析、组合数学、二维偏序、树状数组 CF297E

2026-07-17

7.17外出集训总结

上午：交互题/博弈论/构造专题，还算是听得懂，不过实际自己会不会在考场上打出来就不好说了……
- Tricks:
  - 博弈论
    - 决策覆盖：A可以到达状态集合C，也可以到达另一个状态之后B到达C，则A必胜。如 AGC127C
    - 操作抵消：必败下A跳出局面后B可以使其回到必败局面。
  - 构造
    - $\times 2 + 1$ （这个不是很明白）如 AGC012C
    - 两方案选一：构造两个方案（互相关联），看哪个符合输出哪个。如 AGC066A
下午是做上午讲过的题目
今晚打算复习/补齐之前的知识
然后看看7/20的题单

2026-07-16

7.16外出集训总结

上午是NOIP模拟赛 (153,rnk27/64)
- T1(100) 赛时认为只有50分，实际100。
  - 由于 $\sum_{i=1}^{n}deg_i = 2m$ ，所以本质不同的 $deg$ 只有 $\sqrt{2*m}$ 种
  - 如此两层循环，复杂度实际只有 $O(2m)$
  - 加上前面的扫描，大概 $O(n+m)$
- T2(36) 是字符串大分类讨论（ $T \leq 3$ ），我分类讨论+KMP骗了 36 分 ( subtask 1,2,4 )
- T3(16) 涉及扫描线、线段树相关，这方面不太清楚，不熟，略微优化的暴力+二分拿了 16 分 ( subtask 1,2 )
- T4(1) 拿了猎奇的 subtask1 的1分，询问0次的情况……
  - 博弈论相关，需要考虑必胜/必败状态
下午讲题、订正
我们几个看起来总榜上靠后……实际上过滤掉本校后剩下的多校学生，我们是在前8的……
GF tql orz

2026-07-15

7.15外出集训总结

上午是自习，打昨日的题目
- 借助了一些题解和AI，打出了动态DP/+树剖的题目……
下午讲字符串专题
- 几乎是直接开讲，就20min过了一遍 KMP、Z函数、Manacher、AC自动机
- 毕竟人家当我们学过
- 而我这方面的压根没学过……
- 还讲了后缀数组（SA）以及后缀自动机（SAM），后缀自动机好像是个很强的东西，可以 O(n) 求出所有子串
- 我啥都没打过……晚修试试把上述的模板题先做了，再去看这些拔高的习题吧……
感觉学不会啊……回校后会再学学吗……？

2026-07-15

麻了，卡了一上午常。
最后开了 __int128 避免取模才卡过去了。

CodeForces的判题机性能堪比一颗土豆，居然比机房电脑运行速度慢差不多两倍……

2026-07-14

7.14 外出集训总结

上午：DP优化专题

矩阵乘法 DP 优化和一些常数优化（如行向量优化、八次一mod优化）
动态DP 带修改的DP
- 我好像缺了不少前置知识，如树链剖分、线段树优化DP?
树上动态DP 树剖、线段树、树形DP相关……
线性基两种操作
- 插入 $n$ 个数
- 求任选其中数，所得异或和（ $a_{i1} \oplus a_{i2} \oplus ... \oplus a_{ik}$ ）的最大/最小值
- 不支持删除

下午：DP优化

讲了大量的题，基本都是开头还能听懂，后面的没学过就不懂了……
主要是一些思路……和数据结构优化……？

晚上主要在翻 OI-wiki 补课……

~~好可怕……感觉啥都不懂……~~

~~还有，食堂的意面真好吃~~

2026-07-13

7.13 外出集训总结

上午：打了NOIP模拟赛 一共四道题。

√ T1: bridge 100pts — 简单的贪心题。
√ T2: game 35pts — 性质发现+博弈。发现了其中一个性质，拿了35pts。说实话第二个性质也不难，可惜没看出来。
T3: color 8pts — 花了不少时间用分类并查集做……只拿了8pts。看不懂正解。
T4: brackets 4pts — 这方面的知识没学过。交了一个暴力。正解贪心+线段树分治+优先队列+一些性质式子的发现。

下午是做出最优解的同学的评讲，老实说听不懂。

不过真是神仙食堂