做题记录-JZTXT

时间	题目编号	来源	主要知识点	小结
2023.5.23	T1	校内模拟赛	dp、计数	将袋鼠按照 \(a,b\) 分别从小到大排序，枚举第一个不在其它袋鼠口袋中的袋鼠，将序列分成了两部分，那么 \(a\) 比其小的和其出边必须都要被匹配，枚举跨过分界线的匹配个数，乘上两边内部的匹配算一下贡献即可。
2023.5.23	Ball Collector	ABC302H	图论、贪心	对于每个点的两个球实际上就是二元关系，让 \(a_i\) 向 \(b_i\) 连边，每个连通块计算个数，用可撤销并查集维护一下即可。
2023.5.23	Split and Insert	AGC062B	dp 、最优化问题	正序不方便记录状态，考虑将操作倒序，那么每次可以选择一个子序列将其放到序列的末尾，让序列变为有序。排序考虑区间 \(\text{dp}\) ，设 \(f_{i,j,k}\) 表示在第 \(k\) 次操作前，让 \([i,j]\) 范围内的数相对顺序正确的最小代价，转移是容易得。
2023.5.23	Mex of Subset Sum	AGC062C	模拟，分类讨论	存在的 \(sum\) 个数太多了，不好统计，考虑维护出 \(mex\) 集合。类似于针对补集考虑。首先将序列排序，记 \(S_i\) 表示考虑完 \(a_1,...,a_i\) 这些数，目前的 \(mex\) 集合，转移按照 \(sum_i\) 和 \(a_{i+1}\) 的大小关系讨论一下即可。