Day 1
多项式 + 生成函数。
学习内容
只学了多项式入门，包括 FFT，NTT，简单的多项式板子，简单的牛顿迭代，简单的 OGF 和 EGF。
【TBD】
做题记录
USACO Feb 铜组 T1
感觉难度不会评的太低。
注意到合法答案只可能形如：\(444\cdots44[5,9]\cdots\)
然后就可以直接数位 DP 了。
设 \(f_{cur,c1,c2,zero}\) 表示考虑到第 \(cur\) 位，是否是连续的前缀 \(4\)，是否合法，是否是前导 \(0\)。
然后转移是自然的。
AT_abc386_e
简单题。
用堆维护当前的可以拓展的方格集合，然后尝试拓展，可以做到 \(O(nm\log nm)\)。
AT_abc386_g
赛时被卡常了，不考虑补题。
看起来像一个二维前缀和的形式，所以考虑大力莫队。
每次增删只需要单点修改，查询小于或大于一个数的数的个数和总和。
然后线段树就被卡常了。
正解感觉是值域分块，总体复杂度 \(O((n+m)\sqrt{n})\)。
Day 2
贪心，博弈，构造。
可以统称为思维题。
学习内容
- 拟阵
拟阵是一个集合子集的集合。
这个集合 \(I\) 满足：
-
\(\empty \in I\);
-
\(A \subseteq B,B\in I \Rightarrow A \in I\);
-
\(A,B \in I,\left |A\right |<\left | B\right |\Rightarrow \exists a \in B,A \cup \left \{ a\right \} \in I\);
第二条性质被称为遗传性，第三条性质被称为交换性。
拟阵贪心性质：对于一个带权拟阵 \((S,I)\)，可以通过每次添加权最大的元素得到 \(I\) 中权最大的集合。
常见符合拟阵性质的集合：最小生成树，线性基。
- SG 函数入门
在公平组合游戏中，SG 函数定义为所有后继状态的 mex。游戏先手必胜当且仅当起始状态的 SG 值非零。
多个游戏的和定义为 SG 函数的异或和。
做题记录
只收录了比较有意思的题。
AT_agc008_b
注意到除了最后一次操作的格子，格子的颜色是自由决定的。
然后就可以枚举最后一次操作的区间，其它贪心地选正或负就行。
AT_agc032_e
首先考虑没有模数的情况，肯定是最小和最大匹配，次小和次大匹配，依次类推。
观察一：在有模数的情况下，以某个点为分界点，前面仿上例单独匹配，下面仿上例单独匹配。并且满足前面的和不超过模数，后面的和超过模数。
观察二：分界点越靠左答案越优。
然后就可以二分分界点，判断答案是否合法。
P1484
考虑一个贪心：每次选择值最大的。
显然是不对的，但是可以这样添加反悔操作：选择 \(a_i\) 时，将 \(a_{i+1}+a_{i-1}-a_i\) 加入决策集合，表示反悔 \(a_i\)，选择 \(a_{i-1}\) 和 \(a_{i+1}\)。
用堆维护。
CF168C（?）
直接打表 SG 函数没有太好的性质，因为问题比较一般。
考虑进一步发掘性质。
注意到操作二不会影响操作一的结果，所以可以将一二分开考虑。
操作一可以进一步递归求解，操作二是一个经典的取石子游戏：每次取 \(1,a,a^2,a^3,\cdots,a^k\)，求它的 SG 函数，打表找出规律：先手必胜当且仅当 \((n+1) \bmod (a+1)\) 为偶数。
然后将两个操作拼在一起就是正解。
AT_agc014_d
简单题。
但是没有固定的套路，需要细致地分析问题本质。
首先对于先手而言，他不会选择叶子，因为后手选父亲就死了。
所以对于后手而言，他只会选择当前节点的相邻节点。
考虑当树存在一种完美匹配时，后手一直选先手的匹配点肯定能获胜。否则一定有一个白点没有被匹配。
所以当树不存在完美匹配时，先手必胜。
AT_agc052_a
诈骗题。
考虑直接构造：\(n\) 个 \(0\)，\(n\) 个 \(1\)，\(1\) 个 \(0\)。
Day 3
模拟赛。
T1：AT_agc018_c
看起来很多人做过。
首先因为 \(x+y+z=n\)，所以可以钦定全选 \(c\)，将 \(a\to a-c,b\to b-c\)。
然后就把问题简化为了 \(z=0\) 的情况。
考虑这样一种贪心方式：将序列按 \(a-b\) 降序排序，以某一个点为界，前面选择 \(a\)，后面选择 \(b\)。
正确性显然，如果我们有一个 \(a\) 在 \(b\) 的后面，把它们两个交换显然不劣。
所以我们枚举分界点，用堆维护前后缀的前 \(k\) 大就行了。总体复杂度 \(O(n \log n)\)
注意特判 \(x,y,z=0\) 的情况，否则会挂 30。
比 std 的反悔贪心或者模拟费用流好写多了。
T2：给定一个序列，二人博弈，从 \(s\) 开始，每次可以使序列 \(a_i\to a_i-1 (a_i>0)\) 或移动至下标 \([i+1,\min(i+1,t)]\)，不能操作者败。要求支持区间加，区间查询胜负。
套着博弈壳子的 DS。
注意到答案只和 \(a_i\) 奇偶性相关，初始最靠近 \(t\) 的偶数是必败位置，它前面 \(k\) 个位置是必胜位置，然后再之前的偶数位置是必败位置，以此类推。
考虑硬上 DS 维护。
然后能看出来是弹飞绵羊。
做完了。
总体复杂度 \(O(n \sqrt{n})\)。
不想补。
学习内容
听说 T1 可以模拟费用流，来学一把。
Day 4
模拟赛。
只会 T1，也没改题。
T1：取石子，两人博弈，先手取一次，后手取两次，不能操作者败。
首先这不是公平组合游戏，所以不能 SG。
考虑大力分讨所有情况。
做完了。
学习内容
继续模拟费用流。
Day 5
数据结构。
学习内容
学习了一类很新的题目：函数复合。
做题记录
UOJ 637
二维偏序比较简单，但是没有那么板的题目。
正难则反，考虑对于每个区间计算序列中不会出现的数的个数。
不难发现，对于一个数 \(x\)，它不会出现在区间 \([l,r]+1\) 的序列中，当且仅当：
-
\(x\) 只出现在 \([l,r]\) 中；
-
\(x-1\) 不出现在 \([l,r]\) 中。
发现把每个区间视为点，那么上面第一个限制是一个 3-side 矩形，而第二个限制是若干个 4-side 矩形，总数不超过 \(O(n)\)，并且两两无交。现在 \(x\) 的区间的点的集合是第一个限制和第二个限制的并集的交集。
同时，第一个矩形和第二个矩形的交集一定是矩形。
然后我们把问题转化为了矩形加，单点查的 ds 问题，扫描线解决之，总体复杂度 \(O(n \log n)\)。
Day 6
树上问题。
学习内容
第一次系统地做还原树问题。
做题记录
首先枚举子集暴力容斥是简单的。现在考虑怎样快速计算容斥式子。
具体地，一个联通块内，不考虑其他限制，合法方案数为：
\[n!!=\prod_{i=1}^{\lfloor \frac{n}{2} \rfloor} (n-2i) \]考虑在这个式子的基础上进行 DP。
设 \(f_{i,j}\) 表示在 \(i\) 子树内联通块大小为 \(j\) 的方案数（考虑容斥系数了）。
根据容斥写出转移：
\[f_{x,i}= \sum_{j+k=i,j \ge 1} f_{x,j}f_{y,k}(i \ge 1) \]\[f_{x,i}=- \sum_{j} (j!!)f_{x,j} \]直接 \(O(n^2)\) 计算即可。
首先常规地，把树链挂在 lca 上计算贡献。
然后在每一个点 \(x\)，我们可以加入的树链分为两类：
-
\(x\) 是树链的一个端点，并且是树链的 lca；
-
其他情况。
对于第一种情况，不难发现选择它只会影响至多一个其他树链不能选，所以选了一定不劣；
对于第二种情况，我们相当于从 \(x\) 的子树中选择两个点。
因为每点的子树数量不超过 \(10\)，考虑装压儿子进行 DP。
设 \(f_{x,s}\) 表示以 \(x\) 为根的子树内，子树为选择的集合为 \(s\)。
不难发现可以枚举任意两棵子树，尝试把它们拼在一起进行转移。
然后做完了。还是很优美的。
总体复杂度 \(O(n^2+m+d^22^d)\)。
Day 7
颐和园 + 北京大学
因为这是学术游记所以我就不写了
Day 8
网络流。
其他图论算法因为太杂加上时间比较紧，弃了。
学习内容
开始研读 @ReTF 的文章专栏。
题目由于个人原因不再放出。
做题记录
收录于：学习笔记：模拟费用流
收录于：学习笔记：网络流建模技巧
Day 10
模拟赛。
偶遇 DS 专场强如怪物拼尽全力无法战胜。
调了一整场 T2。最后在 @Richard_whr 的帮助下成功战胜。
T2 收录于：学习笔记：函数复合类 DS 的一种离线解法
学习内容
同时，学习了一个很有用的科技：学习笔记：值域有交的 FHQ-Treap 的快速合并
Day 11
字符串专题。
但是我在学 SAM，并且总结了一下 NOIP 完就想写的关于 LCA 的专题。
学习内容
【TBD】
【TBD】
标签：2024.12,函数,DS,多校,Day,学习,游记,SG,考虑 From： https://www.cnblogs.com/Kenma/p/18686642