感觉需要记录下每天的收获吧。
10.11
一些杂题。记得补。
10.12
第一场模拟赛，考得很不理想。
T1
事实上赛时已经把条件转换的很彻底了：
$$y=(a+b) \mod p$$
$$c=xa-x’y$$
$$x’<x$$
于是我枚举了 $x$ 并在内层继续枚举 $x’(0≤x’<x)$。
然而，其实我只需要枚举 $x$ 并且判断
$$\frac{xa-c}{y} \mod p<x$$
这个式子是否成立即可 AC 。。。
T2
其实感觉这题 xtq 给的题解做法还是很玄学，只要数据是手造的就可以卡掉了。
不过这个题正解也给了一定启发吧，题目的数据范围都是出题人精心准备的。
于是此题，比 $25$ 大的与比它小的分开处理，巧妙利用了 $2^{25}$ 的大小。
T3
赛时没怎么花时间好好想，其实好好分类讨论一下还是可做的。
T4
题目的数据范围都是出题人精心准备的。这题的数据范围非常的骗人。。。$n≤2 \times 10^5$ 的范围，正解却是 $O(n)$。这说明不能全看数据范围判断正解复杂度。
赛时没有写出一个像样的简明的递推式，最后只写了区间dp拿了20pts。这种能力不知道咋锻炼。
10.13
又很不理想。。。
一上来看了 T2 觉得可以 0-1Trie 水掉，直接开始。第二个样例输出来不对就发现有一点假掉了。开始各种摸索打标记。花了大量的时间却都只完成了异或的部分。甚至直到考试结束都只得了这点分。
还有就是因为最近刚做了比较多的线段树分治，所以看到 T4 跟线段树分治有一点像就直接往那里面想，也浪费了比较多的时间。其实 T1 和 T3 也都不难，却没有时间去思考了。
T1
错误地以为这题正解会是很巧妙地围绕幻方的性质求解，于是开始根本没想到暴力。后来发现广搜一下就可以，就开始写。由于没有手写过哈希表，又错把 unordered_map 记成了插入带 log 询问 $O(1)$。所以其实写出了 AC 代码。。。但本地跑起来要好几秒我以为是 unordered_map 复杂度的问题，于是没交。白白损失100 pts。
T2
异或的部分就是裸的 0-1Trie。
其实看到这道题的时候我第一反应是，当时做 0-1Trie 板子的时候看到的是异或，为什么我自己没有联想到对于与、或的运算该怎么处理。
想了很久自以为没想出好方法，其实想到了 $O(3^{20})$ 枚举子集打标记，这已经是正解了，只要再剪枝一下保证同样的子集不被多次枚举就过掉了。所以这题也是痛失满分。
T3
看道题第一眼就想到如果只有一个黑点的情况很好做，两个黑点的话暴力断一下两个点之间的边然后就做完了。由于是暴力断边，复杂度非常错误。乍一看这么写只能获得10pts的坏成绩。
然而断掉两个黑点之间的边显而易见是可二分的。。。当时却完全没想到。只要在刚才那些只花了一两分钟就思考出来的基础上加个二分就可以获得100pts。
T4
要维护的那个东西可以用 multiset，所以现在还不知道我线段树分治的想法能不能成立。最后订正是线段树合并完成的。
STL 还是要用熟练。
反思？
今天还有就是发现自己有一个非常奇怪的弱点
有一些非常简单的实现问题的方法，在考场上都没有直接想到
比如今天的 T1 刚想到暴力搜索的时候，却完全不知道怎么去搜索。问了一下 pzc 一个给定的初始九宫格到一个给定的目标九宫格最少需要的移动步数怎么求（每次只能交换相邻两格）。pzc 感觉不用思考就说出了转成两个 9 位数然后哈希存一下就可以广搜了。其实这样一个小技巧非常显然，但脑子里就是没这么个想法。
再比如是今天 T3，其实暴力没打一个原因是分太少，还有一个原因是不知道怎么方便处理断边。。。事实上随便往点或者往边上打个 tag 就处理好了。。。
10.14
继续掉分。。。
T1
感觉自己优化的挺好的，运用一系列巧妙的位运算保证了时间复杂度。不过人均100pts。
T2
跟昨天 T2 给我第一感一样，感觉这种问题就应当在以前想到才对。今天出的问题是我自己一直没有看出来这题是莫比乌斯反演。
不过得知这是莫反题后我很快推出了 $\sum_{d|x}{\mu(d)} \sum_{i=l}^{r}{[d|a_i]}$ 。其实二分一下就有70pts，再加些优化就100pts了。然而想到式子了根本不知道怎么写可以保证复杂度。
订正时是参考了一个差分/前缀和的思想。考场上难住我的主要是这个 $a_{l…r}$ ，如果就是单纯的从 $l$ 到 $r$ ，我可能想得到前缀和。不得不说代码实现能力还有待提高吧。
T3
想了一会就觉得是区间dp，但思考了蛮久都只能得到一些很错误的复杂度。看到 $O(n^4)$ 应当拿不了什么分也就没打了。其实 $O(n^4)$ 也还是能获得40pts这么个不差的分数了，如果想得到bitset优化的话 $O(\frac{n^4}{w})$ 应当是有60pts的。
有些信息不需要同时枚举，而可以两个 $dp$ 相互转换。这种能力我现在还弱爆了。这题转移过程优化一下就可以少掉一层循环，$O(n^4) -> O(n^3)$ 。再用上bitset优化就是正解的 $O(\frac{n^3}{w})$ 了。
bitset优化dp
目前对此的理解是，当所有状态都是 $bool$ 时，可以压成位，用bitset优化转移过程。
10.18
考完时估分300pts，实际116pts。挂了太多的分。
T1
一个显然的结论题，不知道为什么考场上写挂了？
不过我的求步数用的树状数组求逆序对，可能不太正确。题解说把要交换的拆成若干个环，个数就是总个数减去环的个数。
T2
比赛的时候一定要对拍！
我为了在比赛前练习一下对拍，恰好这题暴力很好写，于是拿我写的“正解”与暴力进行对拍，结果拍出问题来了。然后改了一下就AC了。
T3
“概率问题如果成环了怎么递推”成为了考场上最困扰我的问题。当时感觉自己已经过掉前两题了，还有大把光阴来切后两题。去W.C.的路上碰到了正在考CMO模拟卷的ljc1301，便前去询问。他看了题后说了句“这不就基环树吗”，然后让我尝试乱搞。我乱搞推了个式子过掉了大样例，于是以为自己手头已经获得300pts了。
结果我的式子挂掉了。最后这题应当需要在断环为链之后维护一个前缀信息和后缀信息。思路懂了懒得补了。
T4
似乎比较有难度，以后再补吧。
10.19
考试结束前40分钟，高二的4个学长出现在了机房。于是开始跟强度和大章开始ACM赛制。
T1
赛时以为询问独立，写了半天写了个4.1kb的65pts代码。
大章直接发现了我的代码只要用set维护一下就可以把询问独立改成询问不独立，即可AC，然而当时的我已经筋疲力尽，于是大章重构后提交，最后获得了30pts的成绩。。。我因此痛失35pts。
不过话说回来，应当得想到用set把我的写法改成正解的。。。
T2
所有人看到这题都觉得是原题。不过ljc找到的原题：集训队作业做题记录Link是给点染色，而这题是给边染色。
注意到对于一个点，如果是偶数条边，只需要每次进入这个点的那条边与离开这个点的边染不同颜色即可。于是将奇数条边的点与 $0$ 号点连边，然后跑欧拉回路，每条边颜色交替染。
无解的情况：当每一个点都是偶数条边但整幅图边数为奇数时无解。结论比较难猜，但也好理解。对于每一个点，按上面的染法进行的话，两种颜色的边的个数是相同的，所以整幅图两种颜色的边的数量是相同的，而总边数是奇数就矛盾了。
T3
一个线性基，还没补。
T4
难度题，以后补吧。
10.20
上分场。不仅是ljc跟Owen带我的ACM场，还是跟强度黑杰哥ACM队伍的交流场。
T1
强度秒杀题。直接可以想到扫描线加权值线段树。我拿暴力对拍后发现我跟强度都写挂了。我写的时候有几个细节错误：一个是在权值线段树上二分前 $k$ 大，应当往右子树走，而我弄成前 $k$ 小了；还有一个问题是一个权值如果加了多次并且次数超过了 $k$，需要一个特判。于是亲手带走了100pts。
T2
我是看了题没啥思路，强度黑杰哥也都没有直接的思路。这时候由于运动会不想加油Owen出现在了机房。他直接开始构造。虽然 Owen 猜到的构造方法假掉了，但还是让我见证了神佬们思考问题的过程。过了一会儿ljc来到了机房，并且直接发现这题是他做过的 MO 题，于是他开始在各种 MO 网站检索。最后发现此题出处是All-Russian MO 2005 Grade Level 9 Day 2 Problem 4。于是建图跑二分图染色了。感觉二分图的题建图挺有趣（难）的。
T3
一道被强度跟Owen秒掉的题。同样是NPSY出来的OIer为什么我如此逊色。我跟Owen说感觉同一个出现频率的点的标识长度应该是相同的，Owen嘟囔了一句“这不显然吗”。然后他直接把dp式子写出来了。
确实是好理解的dp，但我目前真的还是个dp废物，自己还是想不出来。。。
T4
以后补吧。。。
10.21
T1
考虑从小到大加点。考虑到这个了就很好过了。
T2
首先是可以转换成求树上长度为 $k$ 的路径条数，然后跟随pzc写了点分治。其实可以按高度合并做到 $O(n)$ （长链剖分）。
T3
基环树，环上的部分断环为链，单调队列。感觉又是口胡出来但写不出来。
T4
待补。
10.25
T1
需要高精度。考场上直接python了。
T2
感觉是数学基础太拉。
线性无关<=>不在一个平面。于是可以求出法向量，法向量不相同意味着不共线，计算法向量是利用一个叉积。
T3
考场上暴力树形背包写挂了。题解用多项式优化一个换根的过程。超纲。
T4
后缀自动机，超纲。
10.26
很难的杂题，听不大懂
10.27
感觉自己水平还是太菜了。第一题跟pzc拍出错误，第二题跟强度拍出错误。
T1
跟pzc都想错了，直接直径除以2就正确了，我们的dp反而是错误的。
T2
其实不难想到按对答案乘的倍数来排序，但自己没想到，是强度提醒后才得知的。并且自己写还没考虑到基数在不断变化以及覆盖只覆盖最大的。
T3
一个构造题，自己想出了一个构造方法。现在还不知道是不是假掉了，但考场上没有注意到swap(s[i],s[i-1])出现下标为0的情况时交换上来了一个 $0$，这就连很好拿的30pts都挂掉了。
T4
日常T4没记录了
10.28
一道错题三道原题场。全是暑假浙大训练的ACM原题。
赛后询问出题人老师，竟真的如此。
T1
考虑按人和杀手分别为源点跑最短路，然后二分倍数，每次选出可到达的点，看起点是否跟终点在一个连通块。
但是这个做法假掉了！！！跟std错的一样。于是得到了出题人老师的15RMB红包。
实际上仔细想想，得每次二分都重新跑一遍Dij。
其实大章AK想到了，还担心两个log过不去。但被pzc一起干扰了。
T2
这种题自己想不出来总感觉自己是伞兵。
赛时我感觉要求 $n$ 次最短路，爆炸复杂度。我问大章怎么做。
大章：“你为什么要求 $n$ 次最短路？”
我：“不是 $n$ 个怪物吗，每个都得求一遍到 $1$ 的最短路。”
大章：“这 $n$ 个怪物的终点是一样的。”
我：“我是伞兵。”
跟pzc对拍发现我玄学的输出了负数。后来发现原来是没有提前把 $1$ 号点作为关键点。
T3
赛时自己想到了预处理出每个红绿灯刚绿的一瞬间走到最后要多久。但我不知道怎么求右侧第一个红灯在哪里。
老李跟强度使用线段树来维护红绿灯变化周期，从后往前扫，每次加入这个红绿灯红灯的出现时间（相对于终点，即后缀和一下）。最后等于说是线段树实现区间取min单点查询。
2021.11.1
T1
预处理出大于 $i$ 的最小的质数 $nxt_i$。
T2
赛时想到了转换成构造 $\frac{n}{2}$ 条链，但发现不太好构造。。。正解是常见模型差量构造。
T3
一眼就二分，贪心选一下点。
T4
把同构转换出一个 $pre$ 数组后用后缀数组求本质不同子串。
现在是2021.11.11，理论上的20天集训的最后一天。由于开始使用linux作为主要操作系统，落下了好久的内容。现在开始补更吧。
2021.11.2
T1
赛时想到枚举每个点为中点，偶数的时候以边为中点。（不知道哪写挂了）。
11.11补题的时候按深度从小到大的顺序枚举每个点，对每个点都处理出向下 $d_i$ 的答案。预处理出所有深度的答案，询问 $O(1)$ 回答即可。
T2
二分图博弈，留坑：https://zhuanlan.zhihu.com/p/362452453
T3
倍增，太难度了。。。
T4
赛时贺了ld的。结论是断在字典序最小的位置。
2021.11.3
太难了。
2021.11.4
T1
赛时跟随pzc写了线段树维护区间矩阵乘。是第一次写这种写法的题吧。
题解可以 $O(n+q)$ ,具体就是求后缀逆元积的后缀和。
T2T3T4
太难了！
2021.11.8
T1
bitset搞一搞。
T2
把二分的平均值减去得到的double值离散化后用权值线段树维护。
赛时pzc不提醒我我居然都想不到离散化？？？
然后我的线段树常数太大了T飞了。但我的式子也就一前缀max，用树状数组就轻松跑过了。。。
2021.11.9
T1
赛时的代码勾八地MLE了。。。优先队列改成multiset然后动态删东西再卡卡常才能过。
T2T3T4
难度。。。